Handsome Non-Commutative Proof-Nets: perfect matchings, series-parallel orders and Hamiltonian circuits

Sylvain Pogodalla 1 Christian Retoré 2
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 SIGNES - Linguistic signs, grammar and meaning: computational logic for natural language
INRIA Futurs, Université Michel de Montaigne - Bordeaux 3, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : This paper provides a definition of proof-nets for non-commutative linear logic (cyclic linear logic and Lambek calculus) where there are no links, that are small graphs representing the connectives. Instead of a tree like representation with links, the formula is depicted as a graph representing the conclusion up to the algebraic properties of the connectives. In the commutative case the formula is viewed as a cograph. In the non-commutative case it is a more complicated kind of graph which is, roughly speaking, a directed cograph. The criterion consists in the commutative condition plus a bracketing condition.
Type de document :
Rapport
[Research Report] RR-5409, INRIA. 2004, pp.25
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00071248
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 14:51:56
Dernière modification le : mercredi 15 novembre 2017 - 08:10:06
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:04:20

Fichiers

Identifiants

  • HAL Id : inria-00071248, version 1

Citation

Sylvain Pogodalla, Christian Retoré. Handsome Non-Commutative Proof-Nets: perfect matchings, series-parallel orders and Hamiltonian circuits. [Research Report] RR-5409, INRIA. 2004, pp.25. 〈inria-00071248〉

Partager

Métriques

Consultations de la notice

247

Téléchargements de fichiers

143