Paper: Towards Efficient Parsing With Proof-Nets

ACL ID E93-1032
Title Towards Efficient Parsing With Proof-Nets
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1993
  • Alain Lecomte (University of Clermont-Ferrand 2, Clermont-Ferrand France)

This paper presents a method for parsing associative Lambek grammars based on graph- theoretic properties. Connection graphs, which are a simplified version of proof-nets, are actually a mere conservative extension of the earlier method of syntactic connexion, discovered by Ajduckiewicz [1935]. The method amounts to find alternating spanning trees in graphs. A sketch of an algorithm for finding such a tree is provided. Interesting properties of time-complexity for this method are expected. It has some similarities with chart-parsing ([KOnig, 1991, 1992], [Hepple, 1992]) but is different at least in the fact that intervals are here edges and words are vertices (or trees) instead of the contrary in classical chart- parsing.