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 complexity.

Laurent, O., TORTORA DE FALCO, L. (2006). Obsessional cliques: a semantic characterization of bounded time complexity. In Proceedings of the twenty-first annual IEEE symposium on Logic In Computer Science (LICS '06). IEEE Computer Society [10.1109/LICS.2006.37].

Obsessional cliques: a semantic characterization of bounded time complexity

TORTORA DE FALCO, LORENZO
2006-01-01

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 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 complexity.
2006
0-7695-2631-4
Laurent, O., TORTORA DE FALCO, L. (2006). Obsessional cliques: a semantic characterization of bounded time complexity. In Proceedings of the twenty-first annual IEEE symposium on Logic In Computer Science (LICS '06). IEEE Computer Society [10.1109/LICS.2006.37].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/180740
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 9
social impact