Marc Dymetman
Proceedings IJCAI'97, Tokyo August 1997
Recently researchers working in the LFG framework have proposed algorithms for taking advantage of the
implicit context-free components of a unification grammar [Maxwell and Kaplan 1996]. 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 1989, Lang 1994] 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
Report number: