t

Virgile Mogbil, Vincent Rahli

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)

Abstract

The relationship between Boolean proof nets of multiplicative linear logic (APN) and Boolean circuits has been studied [Ter04] in a non-uniform setting. We refine this results by taking care of uniformity: the relationship can be expressed in term of the (Turing) polynomial hierarchy. We give a proofs-as-programs correspondence between proof nets and deterministic as well as non-deterministic Boolean circuits with a uniform depth-preserving simulation of each other. The Boolean proof nets class m&BN(poly) is built on multiplicative and additive linear logic with a polynomial amount of additive connectives as the non-deterministic circuit class NNC (poly) is with non-deterministic variables. We obtain uniform-APN = NC and m&BN(poly) = NNC(poly) = NP. © Springer-Verlag Berlin Heidelberg 2007.

Original languageEnglish
Title of host publicationLogical Foundations of Computer Science - International Symposium, LFCS 2007, Proceedings
Pages401-421
Number of pages21
Volume4514 LNCS
Publication statusPublished - 2007
EventInternational Symposium on Logical Foundations of Computer Science, LFCS 2007 - New York, NY, United States
Duration: 4 Jun 20077 Jun 2007

Conference

ConferenceInternational Symposium on Logical Foundations of Computer Science, LFCS 2007
CountryUnited States
CityNew York, NY
Period4/06/077/06/07

Fingerprint Dive into the research topics of 't'. Together they form a unique fingerprint.

  • Cite this

    Mogbil, V., & Rahli, V. (2007). t. In Logical Foundations of Computer Science - International Symposium, LFCS 2007, Proceedings (Vol. 4514 LNCS, pp. 401-421)