This paper concerns a logical approach to natural language parsing based on proof nets (PNs), i.e. de-sequentialized proofs, of linear logic (LL). In particular, it presents a simple and intuitive syntax for PNs of the cyclic multiplicative fragment of linear logic (CyMLL). The proposed correctness criterion for CyMLL PNs can be considered as the non-commutative counterpart of the famous Danos-Regnier (DR) criterion for PNs of the pure multiplicative fragment (MLL) of LL. The main intuition relies on the fact that any DR-switching (i.e. any correction or test graph for a given PN) can be naturally viewed as a seaweed, i.e. a rootless planar tree inducing a cyclic order on the conclusions of the given PN. Dislike the most part of current syntaxes for non-commutative PNs, our syntax allows a sequentialization for the full class of CyMLL PNs, without requiring these latter must be cut-free. Moreover, we give a simple characterization of CyMLL PNs for Lambek Calculus and thus a geometrical (non inductive) way to parse phrases or sentences by means of Lambek PNs.

Abrusci, V.M., Maieli, R. (2015). Cyclic Multiplicative Proof Nets of Linear Logic with an Application to Language Parsing. In Logic, Language, Information, and Computation (pp.53-68). Springer Berlin Heidelberg [10.1007/978-3-662-47709-0_5].

Cyclic Multiplicative Proof Nets of Linear Logic with an Application to Language Parsing

ABRUSCI, Vito Michele;MAIELI, ROBERTO
2015-01-01

Abstract

This paper concerns a logical approach to natural language parsing based on proof nets (PNs), i.e. de-sequentialized proofs, of linear logic (LL). In particular, it presents a simple and intuitive syntax for PNs of the cyclic multiplicative fragment of linear logic (CyMLL). The proposed correctness criterion for CyMLL PNs can be considered as the non-commutative counterpart of the famous Danos-Regnier (DR) criterion for PNs of the pure multiplicative fragment (MLL) of LL. The main intuition relies on the fact that any DR-switching (i.e. any correction or test graph for a given PN) can be naturally viewed as a seaweed, i.e. a rootless planar tree inducing a cyclic order on the conclusions of the given PN. Dislike the most part of current syntaxes for non-commutative PNs, our syntax allows a sequentialization for the full class of CyMLL PNs, without requiring these latter must be cut-free. Moreover, we give a simple characterization of CyMLL PNs for Lambek Calculus and thus a geometrical (non inductive) way to parse phrases or sentences by means of Lambek PNs.
978-3-662-47708-3
978-3-662-47709-0
978-3-662-47708-3
978-3-662-47709-0
Abrusci, V.M., Maieli, R. (2015). Cyclic Multiplicative Proof Nets of Linear Logic with an Application to Language Parsing. In Logic, Language, Information, and Computation (pp.53-68). Springer Berlin Heidelberg [10.1007/978-3-662-47709-0_5].
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/278220
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact