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.
My Menu
Saved Items

Totality, definability and boolean circuits

Antonio BucciarelliContact Information and Ivano SalvoContact Information

(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


Contact Information Antonio Bucciarelli
Email: buccia@dsi.uniromal.it

Contact Information Ivano Salvo
Email: salvo@dsi.uniromal.it
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb01
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)