---
title: "Charts, Interaction-free Grammars, and the Compact Representation of Ambiguity"
authors:
  - "Marc Dymetman"
doi: ""
url: "https://ijcai.org/proceedings/1997/145"
pdf: "https://ijcai.org/proceedings/1997/0145.pdf"
venue: "Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence"
year: 1997
pages: "1002-1008"
track: "Natural-language Processing and Graphical Presentation"
keywords:
---

# Charts, Interaction-free Grammars, and the Compact Representation of Ambiguity

Marc Dymetman

*Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence*, pages 1002-1008.

## Abstract

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, 19961 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 datastructures 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 "interactionfree" grammars, which generate in a backtrackfree 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 space.