Charts, Interaction-free Grammars, and the Compact Representation of Ambiguity
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Natural-language Processing and Graphical Presentation. Pages 1002-1008.
© 1997 International Joint Conferences on Artificial Intelligence
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.
- [Bar-Hillel et al., 1961] Y. Bar-Hillel. M. Perles, and E Shamir. On formal properties of simple phrase structure grammars. Zeitschrift fur Phonetik, Sprachwissenschaft und Kommunicationsforschung,14:142-172,1961.
- [Billot and Lang, 1989] S. Billot and B. Lang. The structure of shared forests in ambiguous parsing. In 27th Meeting of the Association for Computational Linguistics, 1989.
- [Colmerauer, 1984] A. Colmerauer. Equations and Inequa- tions on Finite and Infinite Trees. In Proceedings of the International Conference on Fifth Generation Computer Systems (FGCS-84), pages 85-99, Tokyo, Japan, Novem- ber 1984. ICOT.
- [Joshi, 1985] A. K. Joshi. How much context-sensitivity is required to provide reasonable structural descriptions: Tree adjoining grammars. In D. Dowty. L. Karttunen, and A. Zwicky. editors. Natural Language Parsing : Psy- cholinguistic, Computational and Theoretical Perspec- tives, pages 206-250. Cambridge University Press. New York.1985.
- Joshi. 1987]
- Aravind K. Joshi. The convergence of mildly context-sensitive grammatical formalisms. Presented at the Workshop on Processing of Linguistic Structure, Santa Cruz. 1987.
- [Kaplan and Bresnan, 1982] R. Kaplan and J. Bresnan. Lex- ical functional grammar: A formal system for grammatical representation. In J. Bresnan. editor. The mental represen- tation of grammatical relations. MIT press, Cambridge.
- MA,1982.
- fLang. 1994]
- Bernard Lang. Recognition can be harder than parsing. Computational Intelligence, 10, 1994.
- [Maxwell and Kaplan, 1990] J. T Maxwell and R. Kaplan. A Method for Disjunctive Constraint Satisfaction. Technical Report SSL-90-06, Xerox Pare. (Palo Alto Research Cen- ter). June 1990.
- [Maxwell and Kaplan, 1993] John T. Maxwell and Ronald M. Kaplan. The interface be- tween phrasal and functional constraints. Computational Linguistics, 19( 4):571-590, December 1993.
- [Maxwell and Kaplan, 1996] John T. Maxwell and Ronald M. Kaplan. An ef- ficient parser for lfg. In First LFG Conference, Grenoble, France, August 1996. http: I / www- c sli . stanford.edu/user/mutt/. Link
- [rPereira and Shieber, 1987] Fernando C. N. Pereira and Stu- art M. Shieber. Prolog and Natural-Language Analysis, volume 10 of CSU Lecture Notes. Chicago University Press. Stanford, 1987.
- rPereira and Warren,l980]
- Fernando C. N. Pereira and David H. D. Warren. Definite clause grammars for lan- guage analysis. Artificial Intelligence, 13:231-278,1980.
- [rPereira and Warren, 1983] Fernando C. N. Pereira and David H. D. Warren. Parsing as deduction. In Proceedings of the 21th Annual Meeting of the Association for Com- putational Linguistics, pages 137-144, MIT. Cambridge, MA. June 1983.
- [Vijay-Shanker and Weir, 1994] K. Vijay-Shanker and D. J. Weir. The equivalence of four extensions of context-free grammars. Mathematical Systems Theory, 27(6):511-546, November/December 1994.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Chart-parsing is a well-known technique for representing compactly the multiple parses of a CF grammar. H n is the input string length, the chart can register all the parses in O( n 3 ) space, although there may be an exponential number of them. Each parse can then be recovered in linear time from the chart.
Chart-parsing can be extended to CF-based unification grammar formalisms such as LFG or OCGs. In this case, however, the valid parses of the input string cannot be recovered so easily from the chart. Interaction between fea ture structures can in theory lead to np-complete complexity: printing the first valid parse may require exponential time.
Such complex interactions are however rare in natural lan guage. There is growing agreement among researchers about the "mild context-sensitiveness" of natural language [Joshi, 1985; Vijay-Shanker and Weir, 19941 This means that NL grammars deviate only minimally in complexity from the context-free class. Thus, although NL grammars written in a unification formalism may appear superficially to be highly context-sensitive, most of the interactions between features tend to be local, so that many of the unification constraints could in principle be replaced by fine-grain context-free rules.
Recently researchers working in the LFG framework have proposed algorithms for taking advantage of the implicit context-free components of a unification grammar. Several related algorithms have been proposed, which rely on a no tion of "disjunctive lazy copy links", a form of information propagation in feature structures which is only triggered in case of possible interactions between features [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 pur pose 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 am biguous representation. This work extends a line of research [Billot and Lang, 1989; Lang, 1994] which stresses the con nection between charts and grammars: a chart can be seen as a specialization of the reference grammar for a given in put 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 pro duced in less time and space.
The paper proceeds in the following way:
- Charts can be seen as grammar specializations. The context-free case is presented first, then the case of CF based unification grammars;
- The rhs of rules can be standardized: the unifications explicitly appearing in the rhs can be standardized to a normal form;
- The notion of a interaction-free, or IF, grammar is in troduced; A unification grammar is called IF when its standardized rules have a certain property which guar antees absence of conflict when expanding the rhs non terminals.
- The chart corresponding to a given input string is gener ally a non-IF grammar. An algorithm which transforms this grammar into an equivalent IF grammar is intro duced.
2 Charts
Charts as grammar specializations For a CFG in Chom sky Normal Form (binary rules), and for an input string of length n, a chart can be built in time 0( n 3 ) and space 0( n 2 ) which recognizes whether the string belongs to the language associated with the grammar. H not only recognition, but also parsing of the string is required, then it is convenient, dur ing the bottom-up construction of the chart, to associate with each edge the collection of combinations of daughter edges from which this edge can be obtained. The augmented chart then requires O(n 3 ) space, but then each parse tree can be recovered in a trivial way by starting from the top edge and following top-down the links between mother and daughter edges. In this way, an exponential number of parse trees can be represented in polynomial space.
It has been remarked in [Billot and Lang, 1989] that an augmented chart for a CFG G, given the input string a, can be viewed as a context-free grammar Ga. generating only a, possibly more than once. Each mother edge A is seen as a nonterminal, and each combination of daughter edges < B, C > associated with A is seen as the rhs B C of a rule whose lhs is A. This rule corresponds to a specific instance of some rule of G. Each top-down traversal of G a generates a parse tree for a which is also a parse tree relative to the full grammar G. We will call the grammar G a a specialization of G for the given input string. 1
1 Charts applied to FSAs More generally, it is possible to di rectly extend chart-parsing, with the same polynomial bounds in time and space, to the situation where the input string of words a is generalized to any finite-state automaton FSA. Chart edges are constructed in the usual way, but they now connect automaton nodes rather than positions in the input string. The chart constructed over F SA can then be seen as a CFG G F sA , a specialization of G. which generates the intersection of the regular language associated with FSA and the CF language associated with G [Lang, 19941. Thus chart-parsing is connected to the closure of context-free languages under intersection with a regular language, and the original proof of this closure property [Bar-Hillel eta/., 1961] can be seen as a
Charts and unification Chart-parsing methods extend nat urally to unification grammars based on a context-free back bone, such as LFG [Kaplan and Bresnan, 1982] or DCG [pereira and Warren, 19801 For ease of exposition, we will use a DCG-like notation, but we believe the results to be ap plicable to any CF-based unification grammar.
Assuming a grammar with binary branching rules, any grammar rule can be written in one of the following forms:
for a non-lexical ruleR, and:
for a lexical ruleS. Nonterminals are written as lowercase let ters, terminals under brackets, and uppercase letters are vari ablesrepresentingfeaturestructures. ThenotationUR(A, B, c) is an abbreviation for the set of unification constraints relating the structures A, B and c that appears in rule R.
For such a grammar, one can construct a chart/grammar specialization for a given input string 2 in the following way:
- One constructs a chart for the CF backbone of the gram mar as in the previous section; This chart can be seen as a specialization of the CF-backbone.
- Each non-lexical rule
of the CF-backbone specialization can be seen as a spe cialization of a rule
of the CF-backbone, where the nonterminals a', b', c' are specializations of the nonterminals a, b, c (that is, a' is the instance of the nonterminal a covering a certain specific substring of the input).
- Each such rule R is augmented into:
where A, B, care fresh variables, and whereUR' is the set of unifications associated with R' in the original gram mar.
- A similar operation is performed for the lexical rules.
The unification grammar obtained by this process is an ex tension of the chart/grammar obtained for the CF-backbone. It is a specialization of the original unification grammar, which is equivalent to this grammar as far as the given input string is concerned. H one uses the specialization grammar in a generation mode. expanding nonterminals top-down and
forerunner (as well as an extension!) of chart-parsing.
2 0r, more generally, any input FSA.
"collecting" the unification constraints, one obtains sets of constraints which collectively describe, when they are jointly satisfiable, feature structures associated with the initial sym bol s of the grammar.
The specialization grammar accepts at most the given input string. Determining whether it does accept this string can however still be a difficult problem. Two cases can occur:
- The chart/grammar for the CF-backbone contains cy cles. that is, there exists some nonterminal A (or equiv alently, edge) in this grammar which calls itself recur sively. This can only happen when the CF-backbone is an infinitely ambiguous CFG. or. in other words, if the given unification grammar is not offline-parsable [Fereira and Warren, 1983]; Offiine-parsability is guar anteed under certain conditions. such as the fact that the CF-backbone does not contain any chain production A --+ B or empty production A --+ f [Kaplan and Bresnan, 19821
When there are cycles in the chart, determining whether there exists a traversal of the (unification) specialization grammar which has satisfiable constraints is in general undecidable.
- The full grammar is offiine-parsable. Then the chart/grammar for the CF-backbone is acyclic. In this case, there are only a finite number of top-down traver sals of the (unification) specialization grammar. For each of the traversals, one can perform unification of the collected constraints. Each traversal for which the constraints are satisfiable gives rise to a feature struc ture solution for the input string (or. more precisely, to a "most general unifier" in Prolog terminology. or a "min imal feature structure" in LFG terminology).
The second ease is by far the most important in grammars naturally occurring in NLP. The recognition problem is then decidable, and all the feature structure solutions can be enu merated in finite time. However, there may be an exponential number of these solutions, and it can be shown that, in gen eral. the problem of determining whether a solution exists is np-complete in the length of the input string (it is easy to sim ulate a boolean satisfaction problem with a non-cyclic unifi cation grammar). With NL grammars, however, such intrin sic complexity apparently does not happen: as was discussed above. NL grammars are "almost" context-free, so that unifi cation features could in principle be "almost" dispensed with, and then, there would be no unification interactions to cope with.
In the remainder of this paper, we will explore ways to transform the specialization chart/grammar obtained for an offiine-parsable grammar in such a way that each top-down traversal leads to a satisfiable set of constraints. Because of the np-completeness property noted above. such transformed chart/grammars could in theory take exponential space, but the situation seems to occur rarely, if ever, with NL grammars.
3 Standardized rules
Standardized unification sets We will use the following notation for a unification constraint:
with 1 < n , 0 < m, and A; # A;' for i # i'. with the following interpr~tation: each A;, Bj is a variable represent ing a feature structure or is a constant representing an atomic feature structure (such as 'sg'. 'love', etc.); l1 , .. . , lm are at tribute labels (such as 'subj'. 'number'. etc.); the first ele ment [A1 , .. . , An] of the constraint, called its identification set, says that the structures A1, . .. , An should be unified, the remaining elements (l1 , B1) , . . . , (lm, Bm) . called access relations, say that the value of the attributelj of A1 (and, there fore, of any A;) is B j · We will also use the notation T for the "impossible" unification constraint (which is never satisfied by any structure). Two simple cases of a unification constraint are of special interest: the constraint [[A, A']] . which indi cates unification of A and A'. and the constraint [[A], (l , B)]. which indicates that B is · accessed from A through the at tribute[.
A finite set of unification constraints is said to be in stan dardized form if it is the singleton { T} or if it has the follow ing properties:
- it does not contain T;
- the identification sets of the constraints are disjoint;
- in any given constraint, an attribute label appears at most once;
- in any given constraint. if any of the A; is a constant, then it is the only one, and also m = 0.
A functional structure, in the sense of LFG or related for malisms,·can be seen as an oriented graph whose edges are labeled by attributes, in such a way that no two edges with the same label originate in the same node. If one distinguishes a certain "root" variable A in a unification constraint set, then this set can be seen as subsuming all the functional structures rooted in a node N A which respect, in the obvious sense. the desaiption expressed by the constraint set. If the set is in standardized form and is different from T. then there exist such structures, and the "minimal" functional structure (or, in Prolog parlance. the most general unifier) which subsumes all these structures is trivially obtainable from this standardized set. One has the following property (see [Colmerauer, 1984] for a slightly different wording of the result):
If U is a constraint set, then one can obtain in lin ear time (in function of the size of U) an equivalent standardized set U', where "equivalent" means: ac cepting the same functional structures.
The reduction proceeds by interleaving two steps:
- H two constraints have non-disjoint identification sets, then replace them by a single constraint having as iden tification set the union of the two identification sets, and having as access relations the union of the access rela tions of the two constraints;
- H a given constraint contains two access relations with the same label (l , B) and (l, C), then eliminate the sec ond of these relations, and add to the constraint set a new constraint [[ B , C]] expressing the identification of B and c.
After a finite number of steps, no more such transforma tions can be done. At this point, two cases can occur: ei ther some identification set contains two different atomic con stants (which indicates unification failure) in which case one replaces the whole constraint set by the singleton T. or this is not so, in which case the unification set is in standardized form.
Standardized rules A grammar rule
is said to be standardized if the unification constraint set UR is in standardized form. From what has just been said, it is clear that any grammar rule can be put in standardized form without altering the structures accepted by the grammar.
4 Interaction-free grammars
From any (binary branching) CF grammar G. one can ob tain a related unification grammar G'. which "registers" the derivations of G. H
is a non-lexical rule of G. then the corresponding rule of G' is:
where A, B, c are fresh variables, and where the constraint ex presses that the left constituent of A is B. its right constituent c. Similarly, for a lexical rule:
of G. the corresponding rule of G' is:
which indicates that the lexical value of A is t.
The grammar G', which we call a a pure derivation gram mar, accepts the same strings as G. and assigns to them a functional description which is just an encoding of the deriva tion tree for G.
It is clear that, in any top-down traversal of G'. the con straints cannot clash. In fact, if one considers the set of con straints collected during such a traversal, it is obvious that this set is a standardized unification set, so that no interaction exists between the different variables.
We now introduce a definition which generalizes the situation obtained with G':
A grammar is called an interaction-free, or IF. grammar, if all its standardized rules are interaction-free, that is, have the following two properties:
- the unification set of the rule is not { T};
- ifB is the variable associated with any rhs non terminal b, then this variable does not appear in the identification set of any unification con straint in the rule.
It can be checked that this condition is respected by gram mar G'. In an interaction-free grammar, any top-down traver sal gives rise to a standardized set of unifications. so that no clash can occur between constraints.
Standardized unification sets and interaction-free rules The choice of representation for unification constraints made in section 3 was obviously not the only one possible. A more standard, but equally expressive, notation for unifica tions would have been:
for access constraints. and:
for equality constraints.
The interest of the notation of section 3 is that the no tion of standardization can be defined in it straighforwardly, and that this last notion is directly related to the property of interaction-freeness. Because of the form of a standardized rule, it is obvious that a variable B that does not appear in the identication set of any unification constraint can be set arbi trarily by the "nonterminal call" b( B), without risk of clash ing with variables set by other nonterminal calls in the rule.
This is to be contrasted with the situation had the more standard notation been used. Consider, in such a notation, the following rule:
In this rule there can be a conflict between the assignments given to B and to c. This is because, implicitly, the value of the 12 attribute in B is equal to c. On the other hand, using the notation of section 3, the standardized rule is written as
which is immediately seen not to be interaction-free: B ap pears in the identification set of the second constraint.
5 Making an acyclic grammar interaction-free
Let us consider the chart/grammar specialization G a of an offiine-parsable grammar G for a string a. This grammar is acyclic, that is, no nonterminal calls itself recursively. We will now introduce an algorithm for transforming G a into an equivalent acyclic IF grammar. We will suppose that the rules of G a have been standardized.
The algorithm works by iteratively replacing non-IF rules of the grammar Ga by equivalent, "more IF", rules, until no non-IF rule remains in the grammar:
- We may suppose that there exists a non-IF rule in the grammar, otherwise we are finished. Let us say that a given ruleR' is below another (different) ruleR" if there is a sequence of rules R1 = R" , R2 , ... , Rn = R' in the grammar such that R; contains in its rhs a nonterminal which appears on the lhs of R; + 1. Because the grammar is acyclic, there must be some non-IF ruleR such that any rule below it is IF; otherwise there would be a non-IF rule which is below itself, which would imply grammar cyclicity.
- TakeR. There exists a nonterminal b(B) in its rhs such that B appears in the identification set of some constraint of R. Partially evaluate b(B) by replacing it with the right-hand sides of the (IF) rules which define b.
- This may produce several different "copies" of R, or none, depending on the number of rules which define b in the grammar. In the latter case, no copy is produced, so that R has disappeared (it was unproductive, that is, could not generate anything.)
- Is some copies of R are produced, standardize them. If, after standardization, the constraint set of the rule is {T}. eliminate the. corresponding rule (it is unproduc tive).
- Go to step 1.
The algorithm terminates after a finite number of steps, be cause in an acyclic grammar, partial evaluation can only be performed a finite number of times.
Also, one can see, by a simple induction, that the IF gram mar obtained only contains productive nonterminals, that is, nonterminals which do generate some string with satisfiable constraints.
Let us consider a simple example. Suppose that the input string is "john read here", and that the chart/grammar special ization is:
s(S) -+ np(NP) vp(VP), [[S], (l,NP), (r,VP)], [ [NP), (n, X)), [ [VP), (n, X)) vp(VP) -+ v(V) a(A), [[VP], (l,V), (r,A), (n,Y)], [ [V], (n, Y)) v (V) -+ [read), [ [V), (lex, read), (n, sg) ) v (V) -+ [read), [ [V), (lex, read), (n, pl)) np (NP) -+ [john), [ [NP), (lex, john), (n, sg) ] a (A) -+ [here), [[A), (lex, here))
where n refers to the attribute 'number'. All rules are IF, apart from the s and vp rules. All the rules below the vp rules are IF. We evaluate partially v(V) in this rule, which gives the two rules:
vp (VP) -+ [read) a (A), [ (V), (lex·, read), (n, sg) J, [[VP), (l,V), (r,A), (n,Y)), [[V), (n,Y)) vp (VP) -+ [read) a (A), [ [V), (lex, read), (n, pl) J, [[VP], (l,V), (r,A), (n,Y)], [(V), (n,Y))
or, after standardization:
vp (VP) -+ [read) a (A), [ [V), (lex, read), (n, sg) J, [[VP], (l,V), (r,A), (n,Y)), [[sg,Y)) vp (VP) -+ [read) a (A), [ [V), (lex, read), (n, pl) ) , [ [VP), (1, V), (r,A), (n, Y)), [ [pl, Y))
These rules are IF, because the nonterminal a( A) does not ap pear in any identification set. The only non-IF rule is now the rule for s, and we partially evaluate np(NP) in this rule, giving, after standardization:
s (S) -+ [john) vp(VP), [ [NP), (lex, john), (n, sg)) [[S), (l,NP), (r,VP)), [[VP], (n,X)], [[X,sg))
This rule is again non-IF. We partially evaluate vp(VP). giving the two rules:
s (S) -+ [john) [read) a (A), [ [V), (lex, read), (n, sg) J , [(VP], (l,V), (r,A), (n,Y)), [[sg,Y)], [ [NP), (lex, john), (n, sg)), [ [S), (1, NP), (r, VP) ), [ [VP), (n, X)), [[X, sg]) s(S) -+ [john) [read) a(A), [ [V), (lex, read), (n, pl) J , [[VP), (l,V), (r,A), (n,Y)), [(pl,Y]), [ [NP), (lex, john), (n, sg) J, [ (S), (1, NP), (r, VP)), [ [VP), (n, X)), [[X, sg))
which, during standardization, become:
s (S) -+ [john) [read) a (A), [ [V), (lex, read), (n, sg)) , [[VP), (l,V), (r,A), (n,Y)), [ [NP), (lex, john), (n, sg) J , [[S), (l,NP), (r,VP)), [ [Y,X,sg)), s(S) -+ [john) [read] a(A), [ [V), (lex, read), (n, pl) J , [[VP), (l,V), (r,A), (n,Y)), [ [NP), (lex, john), (n, sg) J, [(S), (l,NP), (r,VP)), [ [pl, Y,X, sg)),
In the second rule, the constraint [[pl , Y, X, sg]] reduces toT, and so the rule is eliminated. As for the first rule, it is is already standardized, as well as IF. The grammar obtained is now IF.
It should be noted that, in the IF rule obtained for s. the adjunct a( A) is now "free": because A does not appear in any identification set of the rhs, whatever the values A may take, it won't interact anymore with the rule. Thus, even if there were many analyses for the adjunct, this unique rule would take care of all of them. 'This is to be contrasted with the case where we would have evaluated all the nonterminals appear ing in the rhs of the s rule, where each solution for the adjunct would have been explicitly represented along with the others.
The example, although simple, displays the crucial feature of the transformation into IF form: partial evaluation is per formed only in case of need; as soon as a nonterminal can no longer interact with its siblings in a rule, it is not expanded further. If this nonterminal itself has a number of possible so lutions, these solutions are kept "factorized" in the grammar.
Ambiguous structures seen as IF grammars Grammars are a kind of and/or representation: alternative rules for ex panding the same nonterminal correspond to a disjunction, while a string of nonterminals on the rhs of a given rule cor responds to a conjunction.
An acyclic IF grammar with no unproductive non terminals is an efficient representation of the several feature structures it generates: if one traverses this grammar top-down from its initial nonterminal s . then one never backtracks, because all nonterminals are productive, and because the collected con straints cannot clash. Thus one can enumerate all the struc tures in a direct way. Such grammar representations can be likened to finite-state representations for dictionaries, which, although they are more compact than simple lists of words, have for most purposes the same practicality as such lists.
6 Conclusion
This paper has brought together two current lines of research: (i) viewing charts as grammar specializations, and (ii) extend ing chart -like ambiguity packing to unification grammars. By doing so. it has clarified the principles underlying the nature of shared representations, stressed the link between grammars and representations, and opened the way for further applica tions in computational linguistics.
Acknowledgments Thanks for discussions and comments to Max Copperman, Lauri Kartunnen, Bernard Lang, John Maxwell and Fric Villemonte de la Clergerie.
@inproceedings{ijcai1997p145,
title = {Charts, Interaction-free Grammars, and the Compact Representation of Ambiguity},
author = {Dymetman, Marc},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {1002--1008},
year = {1997},
note = {Natural-language Processing and Graphical Presentation},
url = {https://ijcai.org/proceedings/1997/145},
}
TY - CPAPER TI - Charts, Interaction-free Grammars, and the Compact Representation of Ambiguity AU - Dymetman, Marc T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 1002 EP - 1008 UR - https://ijcai.org/proceedings/1997/145 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: