PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Morreale E. Computational complexity of partitioned list algorithms. Internal note IEI-B68-18, 1968.
 
 
Abstract
(English)
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