TY  - JOUR
AU  - Bucciarelli, Antonio
AU  - Salvo, Ivano
PY  - 1998
DA  - 1998//
TI  - Totality, Definability and Boolean Circuits
SP  - 808
EP  - 819
VL  - 1443
PB  - Springer
AB  - In the type frame originating from the flat domain of boolean values, we single out elements which are hereditarily total. We show that these elements can be defined, up to total equivalence, by sequential programs. The elements of an equivalence class of the totality equivalence relation (totality class) can be seen as different algorithms for computing a given set-theoretic boolean function. We show that the bottom element of a totality class, which is sequential, corresponds to the most eager algorithm, and the top to the laziest one. Finally we suggest a link between size of totality classes and a well known measure of complexity of boolean functions, namely their sensitivity.
L1  - http://mclab.di.uniroma1.it/publications/papers/papers/Bucciarelli1998.pdf
UR  - https://doi.org/10.1007/BFb0055104
DO  - 10.1007/BFb0055104
N1  - exported from refbase (http://mclab.di.uniroma1.it/publications/show.php?record=70), last updated on Thu, 22 Nov 2012 14:59:18 +0100
ID  - Bucciarelli+Salvo1998
ER  -