Elamur Research⌕
☰
home / papers / 1993 / The Interface between Phrasal and Functional Constraints

The Interface between Phrasal and Functional Constraints

Paper · 1993 · John T. Maxwell and Ronald M. Kaplan

Summary

Many grammar formalisms, including LFG, GPSG, FUG/HPSG and Definite Clause Grammars, combine a context-free phrasal component with attribute-value (functional) constraints. Parsers usually handle each part with its own techniques. Maxwell and Kaplan argue that the coupling between the two parts is a separate source of computational cost. Context-free parsing is polynomial, but each of the possibly exponentially many trees can carry its own costly constraint problem. So even a fast functional solver can leave the overall system exponential in sentence length.

The authors first analyse the standard hybrid design: an active-chart parser that solves the constraints of each constituent as it is built and discards unsatisfiable edges. This pruning relies on monotonicity and still has an exponential worst case. They then identify further properties of the constraint system that can be exploited and outline alternative interface strategies built on them. Preliminary experiments on a small set of English sentences broadly confirm their analysis. They also report a surprising finding: in some conditions, a strategy that does no pruning in the interface clearly beats one that does.

Key points

  • The paper locates a source of exponential complexity in the phrasal–functional interface itself, separate from the cost inside either component.
  • Simple composition (parse first, then solve each tree's constraints in DNF) is shown to be computationally disastrous for exponentially ambiguous grammars.
  • Interleaved pruning in an augmented active-chart parser, built on Sheil's well-formed substring table, depends on monotonicity. Even so, it remains exponential in the worst case.
  • Throughout, the analysis assumes LFG's ban on nonbranching dominance chains, which guarantees that parsing terminates.
  • The experiments use 20 test sentences about compiler design (listed in Appendix A). Under certain conditions, a strategy without interface pruning outperformed the pruning one.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🔬Palo Alto Research CenterPalo Alto · United States14 works · 8,123 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

🧭 Topics 1Research subjects and languages the work is about.Syntax & grammar formalisms · 214 works

Cite

Cite as John T. Maxwell and Ronald M. Kaplan. 1993. The Interface between Phrasal and Functional Constraints. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@article{maxwell1993interface,
  title = {{The Interface between Phrasal and Functional Constraints}},
  author = {John T. Maxwell and Ronald M. Kaplan},
  journal = {Computational Linguistics},
  year = {1993},
  doi = {10.5555/972500.972501},
  url = {https://doi.org/10.5555/972500.972501}
}

References

34 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Barton, G. Edward; Berwick, Robert C.; and Ristad, Eric Sven (1987). Computational Complexity and Natural Language. The MIT Press. find
  2. Bear, John, and Hobbs, Jerry R. (1988). "Localizing expression of ambiguity." In Proceedings, Second Conference on Applied Natural Language Processing. 235-241. find
  3. Church, Kenneth W., and Patil, Ramesh (1982). "Coping with syntactic ambiguity or how to put the block in the box on the table." Computational Linguistics, 8(3-4), 139-149. find
  4. D6rre, Jochen, and Eisele, Andreas (1990). "Feature logic with disjunctive unification." In Proceedings, COLING-90. find
  5. Earley, J. (1970). "An efficient context-free algorithm." Communications of the ACM, 13, 94-102. find
  6. Gazdar, Gerald; Klein, Ewan; Pullum, Geoffrey; and Sag, Ivan. (1985). Generalized Phrase Structure Grammar. Harvard University Press. find
  7. Godden, K. (1990). "Lazy unification." In Proceedings of the 28th Annual Meeting of the ACL. find
  8. Hasida, K. (1986). "Conditioned unification for natural language processing." In Proceedings of COLING-86, 85-87. find
  9. Johnson, Mark. (1989). The computational complexity of Tomita's algorithm." In Proceedings, International Workshop on Parsing Technologies. 203-208. find
  10. Kaplan, Ronald M. (1973) "A multi-processing approach to natural language." In Proceedings, 1973 National Computer Conference. Montvale, N.J., 435–440. find
  11. Kaplan, Ronald M., and Bresnan, Joan (1982). "Lexical-functional grammar: A formal system for grammatical representation." In The Mental Representation of Grammatical Relations, edited by Joan Bresnan, 173-281. MIT Press. find
  12. Karttunen, Lauri (1986). "D-PATR: A development environment for unification-based grammars." In Proceedings, COLING-86, Bonn, Germany. find
  13. Kasper, Robert (1987). "A unification method for disjunctive feature descriptions." In Proceedings, 25th Annual Meeting of the ACL. find
  14. Kay, Martin (1979). "Functional Grammar." In Proceedings, 5th Annual Meeting of the Berkeley Linguistic Society. find
  15. Kay, Martin (1980). "Algorithm schemata and data structures in syntactic processing." In Readings in Natural Language Processing, edited by Barbara J. Grosz, Karen Sparck-Jones, and Bonnie Lynn Webber, 35-70. Morgan Kaufmann. find
  16. Kay, Martin (1989). "Head-driven parsing." In Proceedings, International Workshop on Parsing Technologies. 52~2. find
  17. Knight, Kevin (1989). "Unification: A multidisciplinary survey." ACM Computing Surveys, 21(1), 93-124. find
  18. Maxwell, John T. III, and Kaplan, Ronald M. (1989). "An overview of disjunctive constraint satisfaction." In Proceedings, International Workshop on Parsing Technologies. find
  19. Nagata, Masaaki (1992). "An empirical study on rule granularity and unification interleaving toward an efficient unification-based parsing system." In Proceedings, COLING-92. 177-183. find
  20. Nakano, Mikio (1991). "Constraint projection: An efficient treatment of disjunctive feature descriptions." In Proceedings, 29th Annual Meeting of the ACL. 307-314. find
  21. Nelson, Greg, and Oppen, Derek C. (1980). "Fast decision procedures based on congruence closure." Journal of the ACM, 27(3), 356-364. find
  22. Pereira, Fernando C. N., and Warren, David H. D. (1980). "Definite clause grammars for language analysis — a survey of the formalism and a comparison with augmented transition networks." Artificial Intelligence, 13(3), 231-278. find
  23. Pollard, Carl, and Sag, Ivan (1987). find
  24. Information-Based Syntax and Semantics. CSLI Lecture Notes, Volume 13. Stanford, CA. find
  25. Schabes, Yves (1991). "Polynomial time and space shift-reduce parsing of arbitrary context-free grammars." In Proceedings, 29th Annual Meeting of the ACL. 106-113. find
  26. Sheil, Beau (1976). "Observations on context-free parsing." In Proceedings, COLING-76. find
  27. Shieber, Stuart (1985). "Using restriction to extend parsing algorithms for complex feature-based formalisms." In Proceedings, 23rd Annual Meeting of the ACL. find
  28. Stock, Oliviero; Falcone, Rino; and Insinnamo, Patrizia (1988). "Island parsing and bidirectional charts." In Proceedings, COLING-88. 636-641. find
  29. Thompson, Henry (1983). "MCHART: a flexible, modular chart parsing system." In Proceedings, AAAI-83. 408-410. find
  30. Tomabechi, Hideto (1991). "Quasi-destructive graph unification." In Proceedings, Second International Workshop on Parsing Technology. 164-171. find
  31. Tomita, Masaru (1986). Efficient Parsing for Natural Language. Kluwer Academic Publishers. find
  32. Wittenburg, Kent, and Barnett, Jim (1988). "Canonical representation in NLP systems design." In Proceedings, Second Conference on Applied Natural Language Processing. 253-259. find
  33. Wroblewski, David A. (1987). "Nondestructive graph unification." In Proceedings, AAAI-87. find
  34. Younger, D. H. (1967). "Recognition and parsing of context-free languages in time n3. " Information and Control, 10, 189-208. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/maxwell-1993-interface-between-phrasal-functional-constraints/