---
title: "The Interface between Phrasal and Functional Constraints (1993)"
description: "The authors first analyse the standard hybrid design: an active-chart parser that solves the… 34 references, cited by 48 papers here."
authors: ["John T. Maxwell", "Ronald M. Kaplan"]
year: 1993
venue: "Computational Linguistics"
source: "https://aclanthology.org/J93-4001/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/maxwell-1993-interface-between-phrasal-functional-constraints/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/maxwell-1993-interface-between-phrasal-functional-constraints/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1993](https://md.research.elamur.ai/free/en/papers/1993/) / The Interface between Phrasal and Functional Constraints

# The Interface between Phrasal and Functional Constraints

**Authors:** [John T. Maxwell](https://md.research.elamur.ai/free/en/authors/john-t-maxwell/) and [Ronald M. Kaplan](https://md.research.elamur.ai/free/en/authors/ronald-m-kaplan/) · **Year:** 1993 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 1993](https://md.research.elamur.ai/free/en/venues/cl/1993/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/J93-4001/) · [PDF](https://aclanthology.org/J93-4001.pdf) · [OpenAlex](https://openalex.org/W2111397047)

**Citations:** 157 citations (OpenAlex, 2026-10-14) · [48](https://md.research.elamur.ai/free/en/papers/maxwell-1993-interface-between-phrasal-functional-constraints/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## 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 Center](https://md.research.elamur.ai/free/en/labs/palo-alto-research-center/) — Research institute, Palo Alto, United States · 14 works · 8,123 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 252 works

🧭 Topics (1): [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/) · 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.

```bibtex
@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}
}
```

- [← previous Towards History-based Grammars: Using Richer Models for Probabilistic Parsing](https://md.research.elamur.ai/free/en/papers/black-1993-history-based-grammars-richer-models/)
- [next → Evaluating Message Understanding Systems: An Analysis of the Third Message Understanding Conference (MUC-3)](https://md.research.elamur.ai/free/en/papers/chinchor-1993-evaluating-message-understanding-systems-analysis/)
- [↑ back to papers of 1993](https://md.research.elamur.ai/free/en/papers/1993/)

## 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](https://scholar.google.com/scholar?q=Barton%2C+G%2E+Edward%3B+Berwick%2C+Robert+C%2E%3B+and+Ristad%2C+Eric+Sven+%281987%29%2E+Computational+Complexity+and+Natural+Language%2E+The+MIT+Press%2E)
2. Bear, John, and Hobbs, Jerry R. (1988). "Localizing expression of ambiguity." In Proceedings, Second Conference on Applied Natural Language Processing. 235-241. [find](https://scholar.google.com/scholar?q=Bear%2C+John%2C+and+Hobbs%2C+Jerry+R%2E+%281988%29%2E+%22Localizing+expression+of+ambiguity%2E%22+In+Proceedings%2C+Second+Conference+on+Applied+Natural+Language+Processing%2E+235%2D241%2E)
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](https://scholar.google.com/scholar?q=Church%2C+Kenneth+W%2E%2C+and+Patil%2C+Ramesh+%281982%29%2E+%22Coping+with+syntactic+ambiguity+or+how+to+put+the+block+in+the+box+on+the+table%2E%22+Computational+Linguistics%2C+8%283%2D4%29%2C+139%2D149%2E)
4. D6rre, Jochen, and Eisele, Andreas (1990). "Feature logic with disjunctive unification." In Proceedings, COLING-90. [find](https://scholar.google.com/scholar?q=D6rre%2C+Jochen%2C+and+Eisele%2C+Andreas+%281990%29%2E+%22Feature+logic+with+disjunctive+unification%2E%22+In+Proceedings%2C+COLING%2D90%2E)
5. Earley, J. (1970). "An efficient context-free algorithm." Communications of the ACM, 13, 94-102. [find](https://scholar.google.com/scholar?q=Earley%2C+J%2E+%281970%29%2E+%22An+efficient+context%2Dfree+algorithm%2E%22+Communications+of+the+ACM%2C+13%2C+94%2D102%2E)
6. Gazdar, Gerald; Klein, Ewan; Pullum, Geoffrey; and Sag, Ivan. (1985). Generalized Phrase Structure Grammar. Harvard University Press. [find](https://scholar.google.com/scholar?q=Gazdar%2C+Gerald%3B+Klein%2C+Ewan%3B+Pullum%2C+Geoffrey%3B+and+Sag%2C+Ivan%2E+%281985%29%2E+Generalized+Phrase+Structure+Grammar%2E+Harvard+University+Press%2E)
7. Godden, K. (1990). "Lazy unification." In Proceedings of the 28th Annual Meeting of the ACL. [find](https://scholar.google.com/scholar?q=Godden%2C+K%2E+%281990%29%2E+%22Lazy+unification%2E%22+In+Proceedings+of+the+28th+Annual+Meeting+of+the+ACL%2E)
8. Hasida, K. (1986). "Conditioned unification for natural language processing." In Proceedings of COLING-86, 85-87. [find](https://scholar.google.com/scholar?q=Hasida%2C+K%2E+%281986%29%2E+%22Conditioned+unification+for+natural+language+processing%2E%22+In+Proceedings+of+COLING%2D86%2C+85%2D87%2E)
9. Johnson, Mark. (1989). The computational complexity of Tomita's algorithm." In Proceedings, International Workshop on Parsing Technologies. 203-208. [find](https://scholar.google.com/scholar?q=Johnson%2C+Mark%2E+%281989%29%2E+The+computational+complexity+of+Tomita%27s+algorithm%2E%22+In+Proceedings%2C+International+Workshop+on+Parsing+Technologies%2E+203%2D208%2E)
10. Kaplan, Ronald M. (1973) "A multi-processing approach to natural language." In Proceedings, 1973 National Computer Conference. Montvale, N.J., 435--440. [find](https://scholar.google.com/scholar?q=Kaplan%2C+Ronald+M%2E+%281973%29+%22A+multi%2Dprocessing+approach+to+natural+language%2E%22+In+Proceedings%2C+1973+National+Computer+Conference%2E+Montvale%2C+N%2EJ%2E%2C+435%2D%2D440%2E)
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](https://scholar.google.com/scholar?q=Kaplan%2C+Ronald+M%2E%2C+and+Bresnan%2C+Joan+%281982%29%2E+%22Lexical%2Dfunctional+grammar%3A+A+formal+system+for+grammatical+representation%2E%22+In+The+Mental+Representation+of+Grammatical+Relations%2C+edited+by+Joan+Bresnan)
12. Karttunen, Lauri (1986). "D-PATR: A development environment for unification-based grammars." In Proceedings, COLING-86, Bonn, Germany. [find](https://scholar.google.com/scholar?q=Karttunen%2C+Lauri+%281986%29%2E+%22D%2DPATR%3A+A+development+environment+for+unification%2Dbased+grammars%2E%22+In+Proceedings%2C+COLING%2D86%2C+Bonn%2C+Germany%2E)
13. Kasper, Robert (1987). "A unification method for disjunctive feature descriptions." In Proceedings, 25th Annual Meeting of the ACL. [find](https://scholar.google.com/scholar?q=Kasper%2C+Robert+%281987%29%2E+%22A+unification+method+for+disjunctive+feature+descriptions%2E%22+In+Proceedings%2C+25th+Annual+Meeting+of+the+ACL%2E)
14. Kay, Martin (1979). "Functional Grammar." In Proceedings, 5th Annual Meeting of the Berkeley Linguistic Society. [find](https://scholar.google.com/scholar?q=Kay%2C+Martin+%281979%29%2E+%22Functional+Grammar%2E%22+In+Proceedings%2C+5th+Annual+Meeting+of+the+Berkeley+Linguistic+Society%2E)
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](https://scholar.google.com/scholar?q=Kay%2C+Martin+%281980%29%2E+%22Algorithm+schemata+and+data+structures+in+syntactic+processing%2E%22+In+Readings+in+Natural+Language+Processing%2C+edited+by+Barbara+J%2E+Grosz%2C+Karen+Sparck%2DJones%2C+and+Bonnie+Lynn+Webber)
16. Kay, Martin (1989). "Head-driven parsing." In Proceedings, International Workshop on Parsing Technologies. 52~2. [find](https://scholar.google.com/scholar?q=Kay%2C+Martin+%281989%29%2E+%22Head%2Ddriven+parsing%2E%22+In+Proceedings%2C+International+Workshop+on+Parsing+Technologies%2E+52%7E2%2E)
17. Knight, Kevin (1989). "Unification: A multidisciplinary survey." ACM Computing Surveys, 21(1), 93-124. [find](https://scholar.google.com/scholar?q=Knight%2C+Kevin+%281989%29%2E+%22Unification%3A+A+multidisciplinary+survey%2E%22+ACM+Computing+Surveys%2C+21%281%29%2C+93%2D124%2E)
18. Maxwell, John T. III, and Kaplan, Ronald M. (1989). "An overview of disjunctive constraint satisfaction." In Proceedings, International Workshop on Parsing Technologies. [find](https://scholar.google.com/scholar?q=Maxwell%2C+John+T%2E+III%2C+and+Kaplan%2C+Ronald+M%2E+%281989%29%2E+%22An+overview+of+disjunctive+constraint+satisfaction%2E%22+In+Proceedings%2C+International+Workshop+on+Parsing+Technologies%2E)
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](https://scholar.google.com/scholar?q=Nagata%2C+Masaaki+%281992%29%2E+%22An+empirical+study+on+rule+granularity+and+unification+interleaving+toward+an+efficient+unification%2Dbased+parsing+system%2E%22+In+Proceedings%2C+COLING%2D92%2E+177%2D183%2E)
20. Nakano, Mikio (1991). "Constraint projection: An efficient treatment of disjunctive feature descriptions." In Proceedings, 29th Annual Meeting of the ACL. 307-314. [find](https://scholar.google.com/scholar?q=Nakano%2C+Mikio+%281991%29%2E+%22Constraint+projection%3A+An+efficient+treatment+of+disjunctive+feature+descriptions%2E%22+In+Proceedings%2C+29th+Annual+Meeting+of+the+ACL%2E+307%2D314%2E)
21. Nelson, Greg, and Oppen, Derek C. (1980). "Fast decision procedures based on congruence closure." Journal of the ACM, 27(3), 356-364. [find](https://scholar.google.com/scholar?q=Nelson%2C+Greg%2C+and+Oppen%2C+Derek+C%2E+%281980%29%2E+%22Fast+decision+procedures+based+on+congruence+closure%2E%22+Journal+of+the+ACM%2C+27%283%29%2C+356%2D364%2E)
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](https://scholar.google.com/scholar?q=Pereira%2C+Fernando+C%2E+N%2E%2C+and+Warren%2C+David+H%2E+D%2E+%281980%29%2E+%22Definite+clause+grammars+for+language+analysis%2D%2Da+survey+of+the+formalism+and+a+comparison+with+augmented+transition+networks%2E%22+Artificial+Int)
23. Pollard, Carl, and Sag, Ivan (1987). [find](https://scholar.google.com/scholar?q=Pollard%2C+Carl%2C+and+Sag%2C+Ivan+%281987%29%2E)
24. Information-Based Syntax and Semantics. CSLI Lecture Notes, Volume 13. Stanford, CA. [find](https://scholar.google.com/scholar?q=Information%2DBased+Syntax+and+Semantics%2E+CSLI+Lecture+Notes%2C+Volume+13%2E+Stanford%2C+CA%2E)
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](https://scholar.google.com/scholar?q=Schabes%2C+Yves+%281991%29%2E+%22Polynomial+time+and+space+shift%2Dreduce+parsing+of+arbitrary+context%2Dfree+grammars%2E%22+In+Proceedings%2C+29th+Annual+Meeting+of+the+ACL%2E+106%2D113%2E)
26. Sheil, Beau (1976). "Observations on context-free parsing." In Proceedings, COLING-76. [find](https://scholar.google.com/scholar?q=Sheil%2C+Beau+%281976%29%2E+%22Observations+on+context%2Dfree+parsing%2E%22+In+Proceedings%2C+COLING%2D76%2E)
27. Shieber, Stuart (1985). "Using restriction to extend parsing algorithms for complex feature-based formalisms." In Proceedings, 23rd Annual Meeting of the ACL. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+%281985%29%2E+%22Using+restriction+to+extend+parsing+algorithms+for+complex+feature%2Dbased+formalisms%2E%22+In+Proceedings%2C+23rd+Annual+Meeting+of+the+ACL%2E)
28. Stock, Oliviero; Falcone, Rino; and Insinnamo, Patrizia (1988). "Island parsing and bidirectional charts." In Proceedings, COLING-88. 636-641. [find](https://scholar.google.com/scholar?q=Stock%2C+Oliviero%3B+Falcone%2C+Rino%3B+and+Insinnamo%2C+Patrizia+%281988%29%2E+%22Island+parsing+and+bidirectional+charts%2E%22+In+Proceedings%2C+COLING%2D88%2E+636%2D641%2E)
29. Thompson, Henry (1983). "MCHART: a flexible, modular chart parsing system." In Proceedings, AAAI-83. 408-410. [find](https://scholar.google.com/scholar?q=Thompson%2C+Henry+%281983%29%2E+%22MCHART%3A+a+flexible%2C+modular+chart+parsing+system%2E%22+In+Proceedings%2C+AAAI%2D83%2E+408%2D410%2E)
30. Tomabechi, Hideto (1991). "Quasi-destructive graph unification." In Proceedings, Second International Workshop on Parsing Technology. 164-171. [find](https://scholar.google.com/scholar?q=Tomabechi%2C+Hideto+%281991%29%2E+%22Quasi%2Ddestructive+graph+unification%2E%22+In+Proceedings%2C+Second+International+Workshop+on+Parsing+Technology%2E+164%2D171%2E)
31. Tomita, Masaru (1986). Efficient Parsing for Natural Language. Kluwer Academic Publishers. [find](https://scholar.google.com/scholar?q=Tomita%2C+Masaru+%281986%29%2E+Efficient+Parsing+for+Natural+Language%2E+Kluwer+Academic+Publishers%2E)
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](https://scholar.google.com/scholar?q=Wittenburg%2C+Kent%2C+and+Barnett%2C+Jim+%281988%29%2E+%22Canonical+representation+in+NLP+systems+design%2E%22+In+Proceedings%2C+Second+Conference+on+Applied+Natural+Language+Processing%2E+253%2D259%2E)
33. Wroblewski, David A. (1987). "Nondestructive graph unification." In Proceedings, AAAI-87. [find](https://scholar.google.com/scholar?q=Wroblewski%2C+David+A%2E+%281987%29%2E+%22Nondestructive+graph+unification%2E%22+In+Proceedings%2C+AAAI%2D87%2E)
34. Younger, D. H. (1967). "Recognition and parsing of context-free languages in time n3. " Information and Control, 10, 189-208. [find](https://scholar.google.com/scholar?q=Younger%2C+D%2E+H%2E+%281967%29%2E+%22Recognition+and+parsing+of+context%2Dfree+languages+in+time+n3%2E+%22+Information+and+Control%2C+10%2C+189%2D208%2E)

*Updated 29 October 2026*