Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Totality, definability and boolean circuits
| |
|
Totality, definability and boolean circuits
Antonio Bucciarelli1 and Ivano Salvo1 
| (1) |
Dipartimento di Scienze dell'Informazione, Université di Roma “La Sapienza”, via Salaria, 113 - 00198 Rome, Italy |
Abstract
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.
Keywords Logical Relations - Scott's Model - PCF - Boolean Circuits
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|