Multiplicative-Additive Focusing for Parsing as Deduction

Glyn Morrill
(Universitat Politècnica de Catalunya)
Oriol Valentín
(Universitat Politècnica de Catalunya)

Spurious ambiguity is the phenomenon whereby distinct derivations in grammar may assign the same structural reading, resulting in redundancy in the parse search space and inefficiency in parsing. Understanding the problem depends on identifying the essential mathematical structure of derivations. This is trivial in the case of context free grammar, where the parse structures are ordered trees; in the case of categorial grammar, the parse structures are proof nets. However, with respect to multiplicatives intrinsic proof nets have not yet been given for displacement calculus, and proof nets for additives, which have applications to polymorphism, are involved. Here we approach multiplicative-additive spurious ambiguity by means of the proof-theoretic technique of focalisation.

In Iliano Cervesato and Carsten Schürmann: Proceedings First International Workshop on Focusing (WoF'15), Suva, Fiji, 23rd November 2015, Electronic Proceedings in Theoretical Computer Science 197, pp. 29–54.
Published: 8th November 2015.

ArXived at: http://dx.doi.org/10.4204/EPTCS.197.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org