DocumentCode
2510359
Title
Obsessional Cliques: A Semantic Characterization of Bounded Time Complexity
Author
Laurent, Olivier ; De Falco, Lorenzo Tortora
Author_Institution
Preuves Programmes Systemes, CNRS, Paris
fYear
0
fDate
0-0 0
Firstpage
179
Lastpage
188
Abstract
We give a semantic characterization of bounded complexity proofs. We introduce the notion of obsessional clique in the relational model of linear logic and show that restricting the morphisms of the category RscrEscrLscr to obsessional cliques yields models of ELL and SLL. Conversely, we prove that these models are relatively complete: an LL proof whose interpretation is an obsessional clique is always an ELL/SLL proof. These results are achieved by introducing a system of ELL/SLL untyped proof-nets, which is both correct and complete with respect to elementary/polynomial time complexity
Keywords
computational complexity; formal logic; theorem proving; ELL-SLL untyped proof-nets; bounded time complexity proofs; elementary time complexity; linear logic relational model; obsessional cliques; polynomial time complexity; semantic characterization; Arithmetic; Computational complexity; Computer science; Cultural differences; Electronic mail; Lighting control; Logic; Mathematical model; Mathematics; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Logic in Computer Science, 2006 21st Annual IEEE Symposium on
Conference_Location
Seattle, WA
ISSN
1043-6871
Print_ISBN
0-7695-2631-4
Type
conf
DOI
10.1109/LICS.2006.37
Filename
1691229
Link To Document