Charts, Interaction-Free Grammars, and the Compact Representation of Ambiguity
| dc.creator | Dymetman, Marc | |
| dc.date | 1997-05-12 | |
| dc.date.accessioned | 2026-07-07T09:10:48Z | |
| dc.date.available | 2026-07-07T09:10:48Z | |
| dc.description | Recently researchers working in the LFG framework have proposed algorithms for taking advantage of the implicit context-free components of a unification grammar [Maxwell 96]. This paper clarifies the mathematical foundations of these techniques, provides a uniform framework in which they can be formally studied and eliminates the need for special purpose runtime data-structures recording ambiguity. The paper posits the identity: Ambiguous Feature Structures = Grammars, which states that (finitely) ambiguous representations are best seen as unification grammars of a certain type, here called ``interaction-free'' grammars, which generate in a backtrack-free way each of the feature structures subsumed by the ambiguous representation. This work extends a line of research [Billot and Lang 89, Lang 94] which stresses the connection between charts and grammars: a chart can be seen as a specialization of the reference grammar for a given input string. We show how this specialization grammar can be transformed into an interaction-free form which has the same practicality as a listing of the individual solutions, but is produced in less time and space. | |
| dc.description | 15 pages (Latex, Postscript), to appear in Proceedings IJCAI-97 | |
| dc.identifier | https://arxiv.org/abs/cmp-lg/9705009 | |
| dc.identifier | http://arxiv.org/abs/cmp-lg/9705009 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/151459 | |
| dc.subject | Computation and Language | |
| dc.title | Charts, Interaction-Free Grammars, and the Compact Representation of Ambiguity | |
| dc.type | text |