Istituto di Scienza e Tecnologie dell'Informazione     
Morreale E. Computational complexity of partitioned list algorithms. Internal note IEI-B68-18, 1968.
Some parementers related to the computational complexity of partitioned list algorithms are evaluated. Specifically an upper bound is computed for the average number of comparisons needed by the most unsophisticated version of a partitioned list algorithm for processing a Boolean function in v variables and u canonical clauses. For the same functions the average memory size required for processing is also computed. Furthermore the minimum memory size necessary for processing any Boolean function in u canonical clauses by either a partitioned or a non - partitioned list algorithm is computed. Results obtained from the above comparisons demonstrate that partitioned list algorithms compare favorably with non - partitioned ones both with regard to the time and the memory required for computation.
Subject Partitioned list algorithms

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional