loading...
Obsessional Cliques: A Semantic Characterization of Bounded Time Complexity
Seattle, Washington August 12-August 15
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2006.3721st Annual IEEE Symposium on Logic i ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Olivier Laurent, Lorenzo Tortora de Falco, "Obsessional Cliques: A Semantic Characterization of Bounded Time Complexity," Logic in Computer Science, Symposium on, pp. 179-188, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/LICS.2006.37,
author = {Olivier Laurent and Lorenzo Tortora de Falco},
title = {Obsessional Cliques: A Semantic Characterization of Bounded Time Complexity},
journal ={Logic in Computer Science, Symposium on},
volume = {0},
year = {2006},
issn = {1043-6871},
pages = {179-188},
doi = {http://doi.ieeecomputersociety.org/10.1109/LICS.2006.37},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Logic in Computer Science, Symposium on
TI - Obsessional Cliques: A Semantic Characterization of Bounded Time Complexity
SN - 1043-6871
SP179
EP188
A1 - Olivier Laurent,
A1 - Lorenzo Tortora de Falco,
PY - 2006
KW - null
VL - 0
JA - Logic in Computer Science, Symposium on
ER -
 
Olivier Laurent, CNRS - Paris 7, France
Lorenzo Tortora de Falco, Roma III, Italy
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 REL 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
Citation:
Olivier Laurent, Lorenzo Tortora de Falco, "Obsessional Cliques: A Semantic Characterization of Bounded Time Complexity," lics, pp.179-188, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.