---
title: "Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars — Eisner 1999"
description: "The authors propose a different approach to dynamic programming. 14 references, cited by 90 papers here."
authors: ["Jason Eisner", "Giorgio Satta"]
year: 1999
venue: "Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics"
source: "https://aclanthology.org/P99-1059/"
doi: "10.3115/1034678.1034748"
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/eisner-1999-efficient-parsing-bilexical-context-free/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/eisner-1999-efficient-parsing-bilexical-context-free/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1999](https://md.research.elamur.ai/free/en/papers/1999/) / Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars

# Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars

**Authors:** [Jason Eisner](https://md.research.elamur.ai/free/en/authors/jason-eisner/) and [Giorgio Satta](https://md.research.elamur.ai/free/en/authors/giorgio-satta/) · **Year:** 1999 · **Venue:** Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics · **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/P99-1059/) · [PDF](https://aclanthology.org/P99-1059.pdf) · [DOI 10.3115/1034678.1034748](https://doi.org/10.3115/1034678.1034748)

**Citations:** [90](https://md.research.elamur.ai/free/en/papers/eisner-1999-efficient-parsing-bilexical-context-free/cited-by/) in our library, of the 140,884 papers whose bibliographies we read

## Summary

The paper addresses syntactic analysis (parsing) for bilexical grammars. In such grammars, each word specifies which dependents it accepts, that is, the grammar takes into account the compatibility of specific word pairs. The strong parsers of the time, by Alshawi, Collins, Charniak and Eisner, are built on probabilistic variants of such grammars. Their standard chart algorithms, including CKY, run in O(n⁵) time in sentence length. As a result, they are too slow without aggressive probabilistic pruning. The authors propose a different approach to dynamic programming. It assembles not only complete constituents but also new intermediate derivation fragments. A child constituent is attached to its parent in two steps, and each step is independent of one of the positions in the sentence. This reduces the complexity to O(n⁴) for bilexical CFGs and for head automaton grammars. For a common special case, "split" automata, the complexity remains O(n³), but with a smaller grammar constant. These results show that lexicalized models can be parsed exactly and considerably faster than previously believed.

## Key points

- **Bilexical CFGs in Chomsky normal form (CNF):** recognition in O(n⁴·max(p, |V_D|²)) instead of O(n⁵·|V_D|³) for CKY. The quantity p denotes the largest count of productions associated with any one pair of terminal symbols. There is also a faster variant in practice, using the HALVE rule, which requires an agenda and a sparse parse chart.
- **Head automaton grammars (Alshawi, 1996):** via reduction to a bilexical CFG, parsing takes O(n⁴·t³), and O(n⁴·t²) for deterministic automata. The reduction also works for stochastic versions.
- **Split HAG:** an algorithm over constituent halves marked with a flip state runs in O(n³·g²·t²), and in O(n³·g²·t) for deterministic automata. The previous result (Eisner, 1997) was O(n³·g³·t²).
- The authors note that all three models of Collins (1997) are suitable for the O(n³) method.
- The same technique is carried over to bilexicalized tree adjoining grammars: O(n⁷) instead of the naive O(n⁸).

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

Fields: [Computing & GPUs](https://md.research.elamur.ai/free/en/shelves/computing/)

Topics: [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/)

## Cite

Cite as: Jason Eisner and Giorgio Satta. 1999. Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars. Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics.

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

```bibtex
@inproceedings{eisner1999efficient,
  title = {{Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars}},
  author = {Jason Eisner and Giorgio Satta},
  booktitle = {Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics},
  year = {1999},
  doi = {10.3115/1034678.1034748},
  url = {https://doi.org/10.3115/1034678.1034748}
}
```

- [← previous The MATE meta-scheme for coreference in dialogues in multiple languages](https://md.research.elamur.ai/free/en/papers/poesio-1999-mate-meta-scheme-coreference-dialogues/)
- [next → Corpus-Based Identification of Non-Anaphoric Noun Phrases](https://md.research.elamur.ai/free/en/papers/bean-1999-corpus-based-identification-non-anaphoric/)
- [↑ back to papers of 1999](https://md.research.elamur.ai/free/en/papers/1999/)

## References

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

1. A. V. Aho and J. D. Ullman. 1972. The Theory of Parsing, Translation and Compiling, volume 1. Prentice-Hall, Englewood Cliffs, NJ. [find](https://scholar.google.com/scholar?q=A%2E+V%2E+Aho+and+J%2E+D%2E+Ullman%2E+1972%2E+The+Theory+of+Parsing%2C+Translation+and+Compiling%2C+volume+1%2E+Prentice%2DHall%2C+Englewood+Cliffs%2C+NJ%2E)
2. H. Alshawi. 1996. Head automata and bilingual tiling: Translation with minimal representations. In Proc. of ACL, pages 167-176, Santa Cruz, CA. [find](https://scholar.google.com/scholar?q=H%2E+Alshawi%2E+1996%2E+Head+automata+and+bilingual+tiling%3A+Translation+with+minimal+representations%2E+In+Proc%2E+of+ACL%2C+pages+167%2D176%2C+Santa+Cruz%2C+CA%2E)
3. Y. Bar-Hillel. 1953. A quasi-arithmetical notation for syntactic description. Language, 29:47-58. [find](https://scholar.google.com/scholar?q=Y%2E+Bar%2DHillel%2E+1953%2E+A+quasi%2Darithmetical+notation+for+syntactic+description%2E+Language%2C+29%3A47%2D58%2E)
4. E. Charniak. 1997. Statistical parsing with a context-free grammar and word statistics. In Proc. o] the l~th AAAI, Menlo Park. [find](https://scholar.google.com/scholar?q=E%2E+Charniak%2E+1997%2E+Statistical+parsing+with+a+context%2Dfree+grammar+and+word+statistics%2E+In+Proc%2E+o%5D+the+l%7Eth+AAAI%2C+Menlo+Park%2E)
5. C. Chelba and F. Jelinek. 1998. Exploiting syntactic structure for language modeling. In Proc. of COLING-ACL. [find](https://scholar.google.com/scholar?q=C%2E+Chelba+and+F%2E+Jelinek%2E+1998%2E+Exploiting+syntactic+structure+for+language+modeling%2E+In+Proc%2E+of+COLING%2DACL%2E)
6. N. Chomsky. 1965. Aspects of the Theory o] Syntax. MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=N%2E+Chomsky%2E+1965%2E+Aspects+of+the+Theory+o%5D+Syntax%2E+MIT+Press%2C+Cambridge%2C+MA%2E)
7. M. Collins and J. Brooks. 1995. Prepositional phrase attachment through a backed-off model. In Proe. of the Third Workshop on Very Large Corpora, Cambridge, MA. [our card](https://md.research.elamur.ai/free/en/papers/collins-1995-prepositional-phrase-attachment-through-backed/)
8. M. Collins. 1997. Three generative, lexicalised models for statistical parsing. In Proc. of the 35th A CL and 8th European A CL, Madrid, July. [our card](https://md.research.elamur.ai/free/en/papers/collins-1997-three-generative-lexicalised-models-statistical/)
9. J. Eisner. 1996. An empirical comparison of probability models for dependency grammar. Technical Report IRCS-96-11, IRCS, Univ. of Pennsylvania. [find](https://scholar.google.com/scholar?q=J%2E+Eisner%2E+1996%2E+An+empirical+comparison+of+probability+models+for+dependency+grammar%2E+Technical+Report+IRCS%2D96%2D11%2C+IRCS%2C+Univ%2E+of+Pennsylvania%2E)
10. J. Eisner. 1997. Bilexical grammars and a cubic-time probabilistic parser. In Proceedings of the ~th Int. Workshop on Parsing Technologies, MIT, Cambridge, MA, September. [find](https://scholar.google.com/scholar?q=J%2E+Eisner%2E+1997%2E+Bilexical+grammars+and+a+cubic%2Dtime+probabilistic+parser%2E+In+Proceedings+of+the+%7Eth+Int%2E+Workshop+on+Parsing+Technologies%2C+MIT%2C+Cambridge%2C+MA%2C+September%2E)
11. R. C. Gonzales and M. G. Thomason. 1978. Syntactic Pattern Recognition. Addison-Wesley, Reading, MA. [find](https://scholar.google.com/scholar?q=R%2E+C%2E+Gonzales+and+M%2E+G%2E+Thomason%2E+1978%2E+Syntactic+Pattern+Recognition%2E+Addison%2DWesley%2C+Reading%2C+MA%2E)
12. M. A. Harrison. 1978. Introduction to Formal Language Theory. Addison-Wesley, Reading, MA. [find](https://scholar.google.com/scholar?q=M%2E+A%2E+Harrison%2E+1978%2E+Introduction+to+Formal+Language+Theory%2E+Addison%2DWesley%2C+Reading%2C+MA%2E)
13. J. E. Hopcroft and J. D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA. q (a) [find](https://scholar.google.com/scholar?q=J%2E+E%2E+Hopcroft+and+J%2E+D%2E+Ullman%2E+1979%2E+Introduction+to+Automata+Theory%2C+Languages+and+Computation%2E+Addison%2DWesley%2C+Reading%2C+MA%2E+q+%28a%29)
14. (h \\< j, q E Qdh) q (i \\<_ h, q E Qdh U {F}, s E (~dh) i4 q (h \\< h', q E Qdh, s' E Qd h,) h q s:6 h (h' \\< h, q • Qdh, s • Qd~, s' • Q. dh) h (b) START: - - q q E Ida MID: - - h 'h [find](https://scholar.google.com/scholar?q=%28h+%5C%3C+j%2C+q+E+Qdh%29+q+%28i+%5C%3C%5F+h%2C+q+E+Qdh+U+%7BF%7D%2C+s+E+%28%7Edh%29+i4+q+%28h+%5C%3C+h%27%2C+q+E+Qdh%2C+s%27+E+Qd+h%2C%29+h+q+s%3A6+h+%28h%27+%5C%3C+h%2C+q+%E2%80%A2+Qdh%2C+s+%E2%80%A2+Qd%7E%2C+s%27+%E2%80%A2+Q%2E+dh%29+h+%28b%29+START%3A+%2D+%2D+q+q+E+Ida+MID%3A+%2D+%2D+h+%27h)