Handsome Non-Commutative Proof-Nets: perfect matchings, series-parallel orders and Hamiltonian circuits
RETORÉ, Christian
Linguistic signs, grammar and meaning: computational logic for natural language [SIGNES]
Linguistic signs, grammar and meaning: computational logic for natural language [SIGNES]
RETORÉ, Christian
Linguistic signs, grammar and meaning: computational logic for natural language [SIGNES]
< Réduire
Linguistic signs, grammar and meaning: computational logic for natural language [SIGNES]
Langue
en
Rapport
Ce document a été publié dans
2004p. 25
Résumé en anglais
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 ...Lire la suite >
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.< Réduire
Mots clés en anglais
proof theory
linear logic
graph theory
perfect matching
cographs
cyclic orders
computational linguistics
lambek calculus
categorial grammars
Origine
Importé de halUnités de recherche