---
title: "An Abstract Machine for Unification Grammars — Wintner 1997"
description: "It first builds a theory of parsing over typed feature structures (TFS). 88 references, cited by 5 papers here."
authors: ["Shuly Wintner"]
year: 1997
venue: "arXiv:cmp-lg/9709013"
source: "https://arxiv.org/abs/cmp-lg/9709013"
doi: "10.48550/arxiv.cmp-lg/9709013"
arxiv: "cmp-lg/9709013"
licence: "arXiv — no licence stated (read only)"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/wintner-1997-abstract-machine-unification-grammars/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/wintner-1997-abstract-machine-unification-grammars/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1997](https://md.research.elamur.ai/free/en/papers/1997/) / An Abstract Machine for Unification Grammars

# An Abstract Machine for Unification Grammars

**Authors:** [Shuly Wintner](https://md.research.elamur.ai/free/en/authors/shuly-wintner/) · **Year:** 1997 · **Venue:** arXiv:cmp-lg/9709013 · **Licence:** arXiv — no licence stated (read only)

**Links:** [Publisher's page](https://arxiv.org/abs/cmp-lg/9709013) · [PDF](https://arxiv.org/pdf/cmp-lg/9709013) · [DOI 10.48550/arxiv.cmp-lg/9709013](https://doi.org/10.48550/arxiv.cmp-lg/9709013) · [arXiv cmp-lg/9709013](https://arxiv.org/abs/cmp-lg/9709013) · [OpenAlex](https://openalex.org/W1881517873)

**Citations:** 14 citations (OpenAlex, 2026-10-14) · 5 in our library, of the 149,439 papers whose bibliographies we read

## Summary
This 1997 Technion doctoral thesis by Shuly (Shalom) Wintner, supervised by Nissim Francez, asks how to run unification-based grammars such as HPSG efficiently without giving up formal rigour. It first builds a theory of parsing over typed feature structures (TFS). The theory covers subsumption and its well-foundedness, abstract feature structures, unification, a linear encoding of structures and multi-rooted structures for representing rules. Parsing is then defined as an operational semantics and proved sound, complete and terminating.

On this basis the author designs AMALIA, an abstract machine for linguistic applications. Grammars and type specifications are compiled into machine instructions, as abstract machines do for logic programming. The thesis also describes an implementation. As an application, it develops an HPSG fragment for Hebrew, focusing on noun phrases, the definite article and noun-noun constructs.

The work matters because it links a declarative grammar formalism, a provably correct parsing model and a compiled execution engine.

## Key points
- The theory section gives proofs of soundness, completeness and termination for parsing, plus a correctness argument for the subsumption check.
- AMALIA's input language specifies a type hierarchy together with grammar rules. Both are compiled: the type hierarchy separately, and rules into machine code.
- The unification engine contrasts feature structures with first-order terms. It specifies a memory layout for TFSs and a step that flattens them.
- The listed optimizations and extensions are:
  - lazy evaluation of feature structures,
  - partial descriptions,
  - empty categories,
  - lexical ambiguity,
  - functional attachments.
- The Hebrew HPSG grammar covers phrase-structure schemata, the internal structure of NPs, the status of the definite article and noun-noun (construct) phrases. The full grammar and the instruction list are given in appendices.

## Interesting ideas
- Treating parsing as an operational semantics makes formal proofs of soundness, completeness and termination possible, rather than testing correctness only on examples.
- Compiling the type hierarchy ahead of time turns type compatibility checks into cheap lookups instead of searches at run time.
- Encoding nested feature structures in a flat, linear form makes them simpler to store, copy and unify inside a machine.
- Lazy evaluation of feature structures defers copying or expansion until a value is actually needed, which saves work on paths that fail.
- Lexical ambiguity is handled inside the parsing machine itself, rather than being resolved beforehand.

## For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

- **I1** (tree): The parser's transition system could be stated formally, so every parse step has a defined meaning and the explainability claims rest on provable properties.
- **I2** (world): The WordNet/FrameNet/Wikidata ontology could be precompiled into a table of compatible or joined types, so entity-type checks in the text world are fast and deterministic.
- **I3** (frames): Frames and role fillers could be kept as flat indexed records, so frame unification and its trace are compact and easy to inspect.
- **I4** (world): Entity states and holdings could be materialized on demand when a question touches them, rather than fully built for every sentence.
- **I5** (tokens): The tagger could pass several candidate analyses for ambiguous words downstream and let later constraints choose among them, keeping the discarded options visible for explanation.

*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

- [Technion – Israel Institute of Technology](https://md.research.elamur.ai/free/en/universities/technion-israel-institute-of-technology/) — University, Haifa, Israel · 54 works · 7,237 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,450 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,296 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 321 works

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

## Cite

Cite as: Shuly Wintner. 1997. An Abstract Machine for Unification Grammars. arXiv:cmp-lg/9709013.

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

```bibtex
@misc{wintner1997abstract,
  title = {{An Abstract Machine for Unification Grammars}},
  author = {Shuly Wintner},
  year = {1997},
  doi = {10.48550/arxiv.cmp-lg/9709013},
  eprint = {cmp-lg/9709013},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.cmp-lg/9709013}
}
```

- [← previous CogNIAC: high precision coreference with limited knowledge and linguistic resources](https://md.research.elamur.ai/free/en/papers/baldwin-1997-cogniac-high-precision-coreference-limited/)
- [next → What brings a higher-order entity into focus of attention? Sentential pronouns in English and Norwegian.](https://md.research.elamur.ai/free/en/papers/borthen-1997-what-brings-higher-order-entity/)
- [↑ back to papers of 1997](https://md.research.elamur.ai/free/en/papers/1997/)

## References

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

1. Aho, Alfred V. and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation and Compiling, volume 1: Parsing. Prentice-Hall, Inc., Englewood Cliffs, N.J. [find](https://scholar.google.com/scholar?q=Aho%2C+Alfred+V%2E+and+Jeffrey+D%2E+Ullman%2E+1972%2E+The+Theory+of+Parsing%2C+Translation+and+Compiling%2C+volume+1%3A+Parsing%2E+Prentice%2DHall%2C+Inc%2E%2C+Englewood+Cliffs%2C+N%2EJ%2E)
2. Aı̈t-Kaci, Hassan. 1991. Warren’s Abstract Machine: A Tutorial Reconstruction. Logic Programming. The MIT Press, Cambridge, Massachusetts. [find](https://scholar.google.com/scholar?q=A%C4%B1%CC%88t%2DKaci%2C+Hassan%2E+1991%2E+Warren%E2%80%99s+Abstract+Machine%3A+A+Tutorial+Reconstruction%2E+Logic+Programming%2E+The+MIT+Press%2C+Cambridge%2C+Massachusetts%2E)
3. Aı̈t-Kaci, Hassan, Robert Boyer, Patrick Lincoln, and Roger Nasr. 1989. Efficient implementation of lattice operations. ACM Transactions on Programming Languages and Systems, 11(1):115–146, January. [↗](https://doi.org/10.1145/59287.59293)
4. Aı̈t-Kaci, Hassan and Roberto Di Cosmo. 1993. Compiling order-sorted feature term unification. PRL Technical Note 7, Digital Paris Research Laboratory, December. [↗](https://doi.org/10.13140/rg.2.1.3398.1841)
5. Aı̈t-Kaci, Hassan and Andreas Podelski. 1993. Towards a meaning of LIFE. Journal of Logic Programming, 16(3-4):195–234, July-August. [↗](https://doi.org/10.1016/0743-1066(93)90043-g)
6. Barton, G. Edward, Robert C. Berwick, and Eric Sven Ristad. 1987. Computational Complexity and Natural Language. Computational Models of Cognition and Perception. MIT Press, Cambridge, Mass. [find](https://scholar.google.com/scholar?q=Barton%2C+G%2E+Edward%2C+Robert+C%2E+Berwick%2C+and+Eric+Sven+Ristad%2E+1987%2E+Computational+Complexity+and+Natural+Language%2E+Computational+Models+of+Cognition+and+Perception%2E+MIT+Press%2C+Cambridge%2C+Mass%2E)
7. Beierle, Christoph and Gregor Meyer. 1994. Run-time type computations in the Warren abstract machine. Journal of Logic Programming, 18:123–148. [↗](https://doi.org/10.1016/0743-1066(94)90049-3)
8. Bentur, Esther, Aviella Angel, and Danit Segev. 1992. Computerized analysis of Hebrew words. Hebrew Linguistics, 36:33–38, December. (in Hebrew). [find](https://scholar.google.com/scholar?q=Bentur%2C+Esther%2C+Aviella+Angel%2C+and+Danit+Segev%2E+1992%2E+Computerized+analysis+of+Hebrew+words%2E+Hebrew+Linguistics%2C+36%3A33%E2%80%9338%2C+December%2E+%28in+Hebrew%29%2E)
9. Bird, Steven. 1990. Constraint-Based Phonology. Ph.D. thesis, University of Edinburgh. [find](https://scholar.google.com/scholar?q=Bird%2C+Steven%2E+1990%2E+Constraint%2DBased+Phonology%2E+Ph%2ED%2E+thesis%2C+University+of+Edinburgh%2E)
10. Bird, Steven. 1992. Finite state phonology in HPSG. In Proceedings of COLING-92, pages 74–80. [find](https://scholar.google.com/scholar?q=Bird%2C+Steven%2E+1992%2E+Finite+state+phonology+in+HPSG%2E+In+Proceedings+of+COLING%2D92%2C+pages+74%E2%80%9380%2E)
11. Calcagno, Mike, Andreas Kathol, and Carl Pollard. 1993. A bibliography of books, theses and articles in or on HPSG. Unpublished manuscript, August. [find](https://scholar.google.com/scholar?q=Calcagno%2C+Mike%2C+Andreas+Kathol%2C+and+Carl+Pollard%2E+1993%2E+A+bibliography+of+books%2C+theses+and+articles+in+or+on+HPSG%2E+Unpublished+manuscript%2C+August%2E)
12. Carpenter, Bob. 1991. Typed feature structures: A generalization of first-order terms. In Vijai Saraswat and Ueda Kazunori, editors, Logic Programming – Proceedings of the 1991 International Symposium, pages 187–201, Cambridge, MA. MIT Press. [find](https://scholar.google.com/scholar?q=Carpenter%2C+Bob%2E+1991%2E+Typed+feature+structures%3A+A+generalization+of+first%2Dorder+terms%2E+In+Vijai+Saraswat+and+Ueda+Kazunori%2C+editors%2C+Logic+Programming+%E2%80%93+Proceedings+of+the+1991+International+Symposium)
13. Carpenter, Bob. 1992a. ALE – the attribute logic engine: User’s guide. Technical report, Laboratory for Computational Linguistics, Philosophy Department, Carnegie Mellon University, Pittsburgh, PA 15213, December. [find](https://scholar.google.com/scholar?q=Carpenter%2C+Bob%2E+1992a%2E+ALE+%E2%80%93+the+attribute+logic+engine%3A+User%E2%80%99s+guide%2E+Technical+report%2C+Laboratory+for+Computational+Linguistics%2C+Philosophy+Department%2C+Carnegie+Mellon+University%2C+Pittsburgh%2C+PA+152)
14. Carpenter, Bob. 1992b. The Logic of Typed Feature Structures. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press. [↗](https://doi.org/10.1017/cbo9780511530098)
15. Chayen, M. J. and Z. Dror. 1976. Introduction to Hebrew Transformational Grammar. University Publishing Projects Ltd., Jerusalem. (in Hebrew). [find](https://scholar.google.com/scholar?q=Chayen%2C+M%2E+J%2E+and+Z%2E+Dror%2E+1976%2E+Introduction+to+Hebrew+Transformational+Grammar%2E+University+Publishing+Projects+Ltd%2E%2C+Jerusalem%2E+%28in+Hebrew%29%2E)
16. Choueka, Yaacov and Yoni Ne’eman. 1995. ”Nakdan-T”, a text vocalizer for modern Hebrew. In Proceedings of the Fourth Bar-Ilan Symposium on Foundations of Artificial Intelligence, June. [find](https://scholar.google.com/scholar?q=Choueka%2C+Yaacov+and+Yoni+Ne%E2%80%99eman%2E+1995%2E+%E2%80%9DNakdan%2DT%E2%80%9D%2C+a+text+vocalizer+for+modern+Hebrew%2E+In+Proceedings+of+the+Fourth+Bar%2DIlan+Symposium+on+Foundations+of+Artificial+Intelligence%2C+June%2E)
17. Cohen, Daniel. 1984. Mechanical Syntactic Analysis of a Hebrew Sentence. Ph.D. thesis, Hebrew University of Jerusalem. (In Hebrew). [find](https://scholar.google.com/scholar?q=Cohen%2C+Daniel%2E+1984%2E+Mechanical+Syntactic+Analysis+of+a+Hebrew+Sentence%2E+Ph%2ED%2E+thesis%2C+Hebrew+University+of+Jerusalem%2E+%28In+Hebrew%29%2E)
18. Dörre, Jochen and Michael Dorna. 1993. CUF – a formalism for linguistic knowledge representation. In Jochen Dörre, editor, Computatioal Aspects of Constrained-Based Linguistic Description I, DYANA-2 delivarable R1.2.A, ILLC/Department of Philosophy, University of Amsterdam, Nieuwe Doelenstraat 15, NL-1012 CP Amsterdam, August. [find](https://scholar.google.com/scholar?q=Do%CC%88rre%2C+Jochen+and+Michael+Dorna%2E+1993%2E+CUF+%E2%80%93+a+formalism+for+linguistic+knowledge+representation%2E+In+Jochen+Do%CC%88rre%2C+editor%2C+Computatioal+Aspects+of+Constrained%2DBased+Linguistic+Description+I%2C+DYANA%2D2)
19. Emerson, E. Allen. 1983. Alternative semantics for temporal logics. Theoretical Computer Science, 26:121–130. [↗](https://doi.org/10.1016/0304-3975(83)90082-8)
20. Erbach, Gregor. 1994. ProFIT: Prolog with features, inheritance and templates. CLAUS Report 42, Computerlinguistik, Universität des Saarlandes, D-66041, Saarbrücken, Germany, July. [↗](https://doi.org/10.48550/arxiv.cmp-lg/9502003)
21. Franz, Alex. 1990. A parser for HPSG. Report CMU-LCL-90-3, Laboratory for Computational Linguistics, Department of Philosophy, Carnegie Mellon University, Pittsburgh, PA 15213, July. [find](https://scholar.google.com/scholar?q=Franz%2C+Alex%2E+1990%2E+A+parser+for+HPSG%2E+Report+CMU%2DLCL%2D90%2D3%2C+Laboratory+for+Computational+Linguistics%2C+Department+of+Philosophy%2C+Carnegie+Mellon+University%2C+Pittsburgh%2C+PA+15213%2C+July%2E)
22. Gazdar, G. E., E. Klein, K. Pullum, and Ivan A. Sag. 1985. Generalized Phrase Structure Grammar. Harvard University Press, Cambridge, Mass. [find](https://scholar.google.com/scholar?q=Gazdar%2C+G%2E+E%2E%2C+E%2E+Klein%2C+K%2E+Pullum%2C+and+Ivan+A%2E+Sag%2E+1985%2E+Generalized+Phrase+Structure+Grammar%2E+Harvard+University+Press%2C+Cambridge%2C+Mass%2E)
23. Gazdar, Gerald and Chris Mellish. 1989. Natural Language Processing in PROLOG. Addison-Wesley. [find](https://scholar.google.com/scholar?q=Gazdar%2C+Gerald+and+Chris+Mellish%2E+1989%2E+Natural+Language+Processing+in+PROLOG%2E+Addison%2DWesley%2E)
24. Gerdemann, Dale. 1993. Troll: Type resolution system – fundamental principles and user’s guide. Unpublished manuscript, September. [find](https://scholar.google.com/scholar?q=Gerdemann%2C+Dale%2E+1993%2E+Troll%3A+Type+resolution+system+%E2%80%93+fundamental+principles+and+user%E2%80%99s+guide%2E+Unpublished+manuscript%2C+September%2E)
25. Gerdemann, Dale and Erhard W. Hinrichs. 1988. Unicorn: A unification parser for attribute-value grammars. Studies in the Linguistic Sciences, 18(2):41– 86. [find](https://scholar.google.com/scholar?q=Gerdemann%2C+Dale+and+Erhard+W%2E+Hinrichs%2E+1988%2E+Unicorn%3A+A+unification+parser+for+attribute%2Dvalue+grammars%2E+Studies+in+the+Linguistic+Sciences%2C+18%282%29%3A41%E2%80%93+86%2E)
26. Glinert, Lewis. 1989. The Grammar of Modern Hebrew. Cambridge University Press, Cambridge. [find](https://scholar.google.com/scholar?q=Glinert%2C+Lewis%2E+1989%2E+The+Grammar+of+Modern+Hebrew%2E+Cambridge+University+Press%2C+Cambridge%2E)
27. Götz, Thilo W. 1994. A normal form for types feature structures. Master’s thesis, Eberhard-Karls Universität, Tübingen, March. [find](https://scholar.google.com/scholar?q=Go%CC%88tz%2C+Thilo+W%2E+1994%2E+A+normal+form+for+types+feature+structures%2E+Master%E2%80%99s+thesis%2C+Eberhard%2DKarls+Universita%CC%88t%2C+Tu%CC%88bingen%2C+March%2E)
28. Haas, Andrew. 1989. A parsing algorithm for unification grammar. Computational Linguistics, 15(4):219–232, December. [find](https://scholar.google.com/scholar?q=Haas%2C+Andrew%2E+1989%2E+A+parsing+algorithm+for+unification+grammar%2E+Computational+Linguistics%2C+15%284%29%3A219%E2%80%93232%2C+December%2E)
29. Hermenegildo, Manuel V. 1986. An Abstract Machine Based Execution Model for Computer Architecture Design and Efficient Implementation of Logic Programs in Parallel. Ph.D. thesis, Department of Computer Science, The University of Texas at Austin, Austin, Texas 78712-1188, August. [↗](https://doi.org/10.20868/upm.thesis.14975)
30. Johnson, Mark. 1988. Attribute-Value Logic and the Theory of Grammar, volume 16 of CSLI Lecture Notes. CSLI, Stanford, California. [find](https://scholar.google.com/scholar?q=Johnson%2C+Mark%2E+1988%2E+Attribute%2DValue+Logic+and+the+Theory+of+Grammar%2C+volume+16+of+CSLI+Lecture+Notes%2E+CSLI%2C+Stanford%2C+California%2E)
31. Kaplan, R. and J. Bresnan. 1982. Lexical functional grammar: A formal system for grammatical representation. In J. Bresnan, editor, The Mental Representation of Grammatical Relations. MIT Press, Cambridge, Mass., pages 173–281. [find](https://scholar.google.com/scholar?q=Kaplan%2C+R%2E+and+J%2E+Bresnan%2E+1982%2E+Lexical+functional+grammar%3A+A+formal+system+for+grammatical+representation%2E+In+J%2E+Bresnan%2C+editor%2C+The+Mental+Representation+of+Grammatical+Relations%2E+MIT+Press%2C+Cambr)
32. Kaplan, Ronald M. 1973. A general syntactic processor. In Randall Rustin, editor, Natural Language Processing, number 8 in Courant Computer Science Symposium. Algorithmics Press, P.O. Box 97, New York, N.Y. 10012, pages 194–241. [find](https://scholar.google.com/scholar?q=Kaplan%2C+Ronald+M%2E+1973%2E+A+general+syntactic+processor%2E+In+Randall+Rustin%2C+editor%2C+Natural+Language+Processing%2C+number+8+in+Courant+Computer+Science+Symposium%2E+Algorithmics+Press%2C+P%2EO%2E+Box+97%2C+New+York)
33. Kasper, Robert T. and William B. Rounds. 1986. A logical semantics for feature structures. In Proceedings of the 24th Annual Meeting of the Association for Computational Linguistics, pages 257–265. [find](https://scholar.google.com/scholar?q=Kasper%2C+Robert+T%2E+and+William+B%2E+Rounds%2E+1986%2E+A+logical+semantics+for+feature+structures%2E+In+Proceedings+of+the+24th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+257%E2%80%93265%2E)
34. Kay, Martin. 1973. The MIND system. In Randall Rustin, editor, Natural Language Processing, number 8 in Courant Computer Science Symposium. Algorithmics Press, P.O. Box 97, New York, N.Y. 10012, pages 155–188. [find](https://scholar.google.com/scholar?q=Kay%2C+Martin%2E+1973%2E+The+MIND+system%2E+In+Randall+Rustin%2C+editor%2C+Natural+Language+Processing%2C+number+8+in+Courant+Computer+Science+Symposium%2E+Algorithmics+Press%2C+P%2EO%2E+Box+97%2C+New+York%2C+N%2EY%2E+10012%2C+pages)
35. Kay, Martin. 1983. Unification grammar. Technical report, Xerox Palo Alto Research Center, Palo Alto, CA. [find](https://scholar.google.com/scholar?q=Kay%2C+Martin%2E+1983%2E+Unification+grammar%2E+Technical+report%2C+Xerox+Palo+Alto+Research+Center%2C+Palo+Alto%2C+CA%2E)
36. King, Paul. 1989. A Logical Formalism for HPSG. Doctoral dissertation, University of Manchester, Manchester, UK. [find](https://scholar.google.com/scholar?q=King%2C+Paul%2E+1989%2E+A+Logical+Formalism+for+HPSG%2E+Doctoral+dissertation%2C+University+of+Manchester%2C+Manchester%2C+UK%2E)
37. King, Paul. 1992. Unification grammars and descriptive formalisms: Lecture notes for a graduate level course. Unpublished manuscript. [find](https://scholar.google.com/scholar?q=King%2C+Paul%2E+1992%2E+Unification+grammars+and+descriptive+formalisms%3A+Lecture+notes+for+a+graduate+level+course%2E+Unpublished+manuscript%2E)
38. Kodric̆, Sandi, Fred Popowich, and Carl Vogel. 1992. The HPSG-PL system. CSS-IS TR 92-05, School of Computing Science, Centre for Systems Science, Simon Fraser University, Burnaby, B. C. Canada V5A 1S6, Jun. [find](https://scholar.google.com/scholar?q=Kodric%CC%86%2C+Sandi%2C+Fred+Popowich%2C+and+Carl+Vogel%2E+1992%2E+The+HPSG%2DPL+system%2E+CSS%2DIS+TR+92%2D05%2C+School+of+Computing+Science%2C+Centre+for+Systems+Science%2C+Simon+Fraser+University%2C+Burnaby%2C+B%2E+C%2E+Canada+V5A+1S)
39. Kolliakou, Dimitra. 1996. Definiteness and the make-up of nominal categories. In Claire Grover and Enric Vallduvı́, editors, Studies in HPSG, volume 12 of Edinburgh Working Papers in Cognitive Science. Centre for Cognitive Science, The University of Edinburgh, chapter 4, pages 121–164. [find](https://scholar.google.com/scholar?q=Kolliakou%2C+Dimitra%2E+1996%2E+Definiteness+and+the+make%2Dup+of+nominal+categories%2E+In+Claire+Grover+and+Enric+Vallduv%C4%B1%CC%81%2C+editors%2C+Studies+in+HPSG%2C+volume+12+of+Edinburgh+Working+Papers+in+Cognitive+Science)
40. Kursawe, Peter. 1987. How to invent a Prolog machine. New Generation Computing, 5:97–114. [↗](https://doi.org/10.1007/bf03037460)
41. Landin, P. J. 1964. The mechanical evaluation of expressions. The Computer Journal, 6(4):308–320. [↗](https://doi.org/10.1093/comjnl/6.4.308)
42. Lloyd, John Wylie. 1987. Foundations of Logic Programming. Springer series in Symbolic Computation – Artificial Intelligence. Springer, Berlin, second edition. [↗](https://doi.org/10.1007/978-3-642-83189-8)
43. Manaster-Ramer, Alexis. 1987. Mathematics of Language. John Benjamins Publishing Company, Amsterdam/Philadelphia. [find](https://scholar.google.com/scholar?q=Manaster%2DRamer%2C+Alexis%2E+1987%2E+Mathematics+of+Language%2E+John+Benjamins+Publishing+Company%2C+Amsterdam%2FPhiladelphia%2E)
44. Moshier, Drew. 1988. Extensions to Unification Grammars for the Description of Programming Languages. Ph.D. thesis, University of Michigan, Ann Arbor. [find](https://scholar.google.com/scholar?q=Moshier%2C+Drew%2E+1988%2E+Extensions+to+Unification+Grammars+for+the+Description+of+Programming+Languages%2E+Ph%2ED%2E+thesis%2C+University+of+Michigan%2C+Ann+Arbor%2E)
45. Moshier, Drew M. and William C. Rounds. 1987. A logic for partially specified data structures. In 14th Annual ACM Symposium on Principles of Programming Languages, pages 156–167, January. [find](https://scholar.google.com/scholar?q=Moshier%2C+Drew+M%2E+and+William+C%2E+Rounds%2E+1987%2E+A+logic+for+partially+specified+data+structures%2E+In+14th+Annual+ACM+Symposium+on+Principles+of+Programming+Languages%2C+pages+156%E2%80%93167%2C+January%2E)
46. Müller, Stefan. 1996. HPSG literature. Available as an electronic document at [http://cl-www.dfki.uni-sb.de/HPSG/](http://cl-www.dfki.uni-sb.de/HPSG/). [↗](http://cl-www.dfki.uni-sb.de/HPSG/)
47. Nerbonne, John. 1992. Feature-based lexicons: An example and a comparison to DATR. Research Report RR-92-04, Deutsches Forschungszentrum für Künstliche Intelligenz GmbH, February. [↗](https://doi.org/10.22028/d291-24838)
48. Nerbonne, John, Klaus Netter, and Carl Pollard, editors. 1994. German in Head-Driven Phrase Structure Grammar. Number 46 in CSLI lecture notes. CSLI, Stanford, Ca. [find](https://scholar.google.com/scholar?q=Nerbonne%2C+John%2C+Klaus+Netter%2C+and+Carl+Pollard%2C+editors%2E+1994%2E+German+in+Head%2DDriven+Phrase+Structure+Grammar%2E+Number+46+in+CSLI+lecture+notes%2E+CSLI%2C+Stanford%2C+Ca%2E)
49. Netter, Klaus. 1994. Towards a theory of functional heads. In John Nerbonne, Klaus Netter, and Carl Pollard, editors, German in Head-Driven Phrase Structure Grammar, volume 46 of CSLI Lecture Notes. CSLI, Stanford, CA, chapter 9, pages 297–340. [find](https://scholar.google.com/scholar?q=Netter%2C+Klaus%2E+1994%2E+Towards+a+theory+of+functional+heads%2E+In+John+Nerbonne%2C+Klaus+Netter%2C+and+Carl+Pollard%2C+editors%2C+German+in+Head%2DDriven+Phrase+Structure+Grammar%2C+volume+46+of+CSLI+Lecture+Notes%2E+C)
50. Nilsson, Ulf. 1993. Towards a methodology for the design of abstract machines for logic programming languages. Journal of Logic Programming, 16:163–189. [↗](https://doi.org/10.1016/0743-1066(93)90026-d)
51. Nirenburg, Sergei and Yosef Ben-Asher. 1984. HUHU – the Hebrew University Hebrew understander. Computer Languages, 9(3/4). [↗](https://doi.org/10.1016/0096-0551(84)90003-1)
52. Ornan, Uzzi. 1964. Noun Phrases in Modern Hebrew Literature. Ph.D. thesis, Hebrew University, Jerusalem. (in Hebrew). [find](https://scholar.google.com/scholar?q=Ornan%2C+Uzzi%2E+1964%2E+Noun+Phrases+in+Modern+Hebrew+Literature%2E+Ph%2ED%2E+thesis%2C+Hebrew+University%2C+Jerusalem%2E+%28in+Hebrew%29%2E)
53. Ornan, Uzzi. 1979. The Simple Sentence. Academon, Jerusalem, Israel. (in Hebrew). [find](https://scholar.google.com/scholar?q=Ornan%2C+Uzzi%2E+1979%2E+The+Simple+Sentence%2E+Academon%2C+Jerusalem%2C+Israel%2E+%28in+Hebrew%29%2E)
54. Ornan, Uzzi. 1986. Phonemic script: A central vehicle for processing natural language – the case of Hebrew. Technical Report 88.181, IBM Research Center, Haifa, Israel. [find](https://scholar.google.com/scholar?q=Ornan%2C+Uzzi%2E+1986%2E+Phonemic+script%3A+A+central+vehicle+for+processing+natural+language+%E2%80%93+the+case+of+Hebrew%2E+Technical+Report+88%2E181%2C+IBM+Research+Center%2C+Haifa%2C+Israel%2E)
55. Ornan, Uzzi. 1994. Basic concepts in ”romanization” of scripts. Technical Report LCL 94-5, Laboratory for Computational Linguistics, Technion, Haifa, Israel, March. [find](https://scholar.google.com/scholar?q=Ornan%2C+Uzzi%2E+1994%2E+Basic+concepts+in+%E2%80%9Dromanization%E2%80%9D+of+scripts%2E+Technical+Report+LCL+94%2D5%2C+Laboratory+for+Computational+Linguistics%2C+Technion%2C+Haifa%2C+Israel%2C+March%2E)
56. Ornan, Uzzi and Michael Katz. 1995. A new program for Hebrew index based on the Phonemic Script. Technical Report LCL 94-7, Laboratory for Computational Linguistics, Technion, Haifa, Israel, July. [find](https://scholar.google.com/scholar?q=Ornan%2C+Uzzi+and+Michael+Katz%2E+1995%2E+A+new+program+for+Hebrew+index+based+on+the+Phonemic+Script%2E+Technical+Report+LCL+94%2D7%2C+Laboratory+for+Computational+Linguistics%2C+Technion%2C+Haifa%2C+Israel%2C+July%2E)
57. Ousterhout, John K. 1994. Tcl and the Tk Toolkit. Addison-Wesley Professional Computing Series. Addison-Wesley. [find](https://scholar.google.com/scholar?q=Ousterhout%2C+John+K%2E+1994%2E+Tcl+and+the+Tk+Toolkit%2E+Addison%2DWesley+Professional+Computing+Series%2E+Addison%2DWesley%2E)
58. Penn, Gerald. 1993. A comprehensive HPSG grammar in ALE. Technical report, Laboratory for Computational Linguistics, Carnegie Mellon University, Pittsburgh, PA. [find](https://scholar.google.com/scholar?q=Penn%2C+Gerald%2E+1993%2E+A+comprehensive+HPSG+grammar+in+ALE%2E+Technical+report%2C+Laboratory+for+Computational+Linguistics%2C+Carnegie+Mellon+University%2C+Pittsburgh%2C+PA%2E)
59. Pereira, Fernando C. N. and David H. D. Warren. 1983. Parsing as deduction. In Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics, pages 137–144, June. [find](https://scholar.google.com/scholar?q=Pereira%2C+Fernando+C%2E+N%2E+and+David+H%2E+D%2E+Warren%2E+1983%2E+Parsing+as+deduction%2E+In+Proceedings+of+the+21st+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+137%E2%80%93144%2C+June%2E)
60. Pollard, Carl and Ivan A. Sag. 1987. Information Based Syntax and Semantics. Number 13 in CSLI Lecture Notes. CSLI. [find](https://scholar.google.com/scholar?q=Pollard%2C+Carl+and+Ivan+A%2E+Sag%2E+1987%2E+Information+Based+Syntax+and+Semantics%2E+Number+13+in+CSLI+Lecture+Notes%2E+CSLI%2E)
61. Pollard, Carl and Ivan A. Sag. 1994. Head-Driven Phrase Structure Grammar. University of Chicago Press and CSLI Publications. [find](https://scholar.google.com/scholar?q=Pollard%2C+Carl+and+Ivan+A%2E+Sag%2E+1994%2E+Head%2DDriven+Phrase+Structure+Grammar%2E+University+of+Chicago+Press+and+CSLI+Publications%2E)
62. Pollard, Carl J. and M. Drew Moshier. 1990. Unifying partial descriptions of sets. In Philip P. Hanson, editor, Information, Language and Cognition, volume 1 of Vancouver Studies in Cognitive Science. University of British Columbia Press, Vancouver 1990, chapter 10, pages 285–322. [find](https://scholar.google.com/scholar?q=Pollard%2C+Carl+J%2E+and+M%2E+Drew+Moshier%2E+1990%2E+Unifying+partial+descriptions+of+sets%2E+In+Philip+P%2E+Hanson%2C+editor%2C+Information%2C+Language+and+Cognition%2C+volume+1+of+Vancouver+Studies+in+Cognitive+Science%2E)
63. Popowich, Fred and Carl Vogel. 1991. A logic-based implementation of head-driven phrase structure grammar. In Charles Grant Brown and Gregers Koch, editors, Natural Language Understanding and Logic Programming, III, pages 227–245. Elsevier Science Publishers (North-Holland). [find](https://scholar.google.com/scholar?q=Popowich%2C+Fred+and+Carl+Vogel%2E+1991%2E+A+logic%2Dbased+implementation+of+head%2Ddriven+phrase+structure+grammar%2E+In+Charles+Grant+Brown+and+Gregers+Koch%2C+editors%2C+Natural+Language+Understanding+and+Logic+Pr)
64. Prudian, Derek and Carl Pollard. 1985. Parsing head-driven phrase structure grammar. In Proceedings of the 23rd Annual Meeting of the Association for Computational Linguistics, Chicago, IL. University of Chicago. [find](https://scholar.google.com/scholar?q=Prudian%2C+Derek+and+Carl+Pollard%2E+1985%2E+Parsing+head%2Ddriven+phrase+structure+grammar%2E+In+Proceedings+of+the+23rd+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+Chicago%2C+IL%2E+University)
65. Russell, Dale W. 1993. Language Acquisition in a Unification-Based Grammar Processing System Using a Real-World Knowledge Base. Ph.D. thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, July. [find](https://scholar.google.com/scholar?q=Russell%2C+Dale+W%2E+1993%2E+Language+Acquisition+in+a+Unification%2DBased+Grammar+Processing+System+Using+a+Real%2DWorld+Knowledge+Base%2E+Ph%2ED%2E+thesis%2C+Department+of+Computer+Science%2C+University+of+Illinois+at+)
66. Russinoff, David M. 1992. A verified Prolog compiler for the Warren Abstract Machine. Journal of Logic Programming, 13:367–412. [↗](https://doi.org/10.1016/0743-1066(92)90054-7)
67. Sag, Ivan A. and Janet Dean Fodor. 1994. Extraction without traces. In Raul Aranovich, William Byrne, Susanne Preuss, and Martha Senturia, editors, Proceedings of the Thirteenth West Coast Conference on Formal Linguistics, Stanford. CSLI Publications/SLA. [find](https://scholar.google.com/scholar?q=Sag%2C+Ivan+A%2E+and+Janet+Dean+Fodor%2E+1994%2E+Extraction+without+traces%2E+In+Raul+Aranovich%2C+William+Byrne%2C+Susanne+Preuss%2C+and+Martha+Senturia%2C+editors%2C+Proceedings+of+the+Thirteenth+West+Coast+Conference+)
68. Samuelsson, Christer. 1995. An efficient algorithm for surface generation. In Proceedings of the International Joint Conference on Artificial Intelligence. [↗](https://doi.org/10.48550/arxiv.cmp-lg/9507007)
69. Schumann, Johann M. Ph. 1991. Efficient Theorem Provers based on an Abstract Machine. Ph.D. thesis, Technische Universität München, Institut Für Informatik. [find](https://scholar.google.com/scholar?q=Schumann%2C+Johann+M%2E+Ph%2E+1991%2E+Efficient+Theorem+Provers+based+on+an+Abstract+Machine%2E+Ph%2ED%2E+thesis%2C+Technische+Universita%CC%88t+Mu%CC%88nchen%2C+Institut+Fu%CC%88r+Informatik%2E)
70. Shieber, Stuart M. 1985. Using restriction to extend parsing algorithms for complex-feature-based formalisms. In Proceedings of the 23rd Annual Meeting of the ACL, pages 145– 152, July. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+M%2E+1985%2E+Using+restriction+to+extend+parsing+algorithms+for+complex%2Dfeature%2Dbased+formalisms%2E+In+Proceedings+of+the+23rd+Annual+Meeting+of+the+ACL%2C+pages+145%E2%80%93+152%2C+July%2E)
71. Shieber, Stuart M. 1986. An Introduction to Unification Based Approaches to Grammar. CSLI Lecture Notes. CSLI. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+M%2E+1986%2E+An+Introduction+to+Unification+Based+Approaches+to+Grammar%2E+CSLI+Lecture+Notes%2E+CSLI%2E)
72. Shieber, Stuart M. 1992. Constraint-Based Grammar Formalisms. MIT Press, Cambridge, Mass. [↗](https://doi.org/10.7551/mitpress/2123.001.0001)
73. Shieber, Stuart M., Yves Schabes, and Fernando C. N. Pereira. 1994. Principles and implementation of deductive parsing. Technical Report TR-11-94, Center for Research in Computing Technology, Division of Applied Sciences, Harvard University, April. [↗](https://doi.org/10.1016/0743-1066(95)00035-i)
74. Sikkel, Klaas. 1993. Parsing Schemata. Klaas Sikkel, Enschede. [find](https://scholar.google.com/scholar?q=Sikkel%2C+Klaas%2E+1993%2E+Parsing+Schemata%2E+Klaas+Sikkel%2C+Enschede%2E)
75. Smolka, Gert. 1988. A feature logic with subsorts. LILOG Report 33, IBM Deutschland, May. [find](https://scholar.google.com/scholar?q=Smolka%2C+Gert%2E+1988%2E+A+feature+logic+with+subsorts%2E+LILOG+Report+33%2C+IBM+Deutschland%2C+May%2E)
76. Smolka, Gert and Ralf Treinen. 1994. Records for logic programming. Journal of Logic Programming, 18:229–258. [↗](https://doi.org/10.1016/0743-1066(94)90044-2)
77. Swift, Terrance and David Warren. 1993. Compiling OLDT evaluation: Background and overview. Technical Report 92/04, SUNY Stony Brook, March. [find](https://scholar.google.com/scholar?q=Swift%2C+Terrance+and+David+Warren%2E+1993%2E+Compiling+OLDT+evaluation%3A+Background+and+overview%2E+Technical+Report+92%2F04%2C+SUNY+Stony+Brook%2C+March%2E)
78. Warren, David H. D. 1983. An abstract Prolog instruction set. Technical Note 309, SRI International, Menlo Park, CA., August. [find](https://scholar.google.com/scholar?q=Warren%2C+David+H%2E+D%2E+1983%2E+An+abstract+Prolog+instruction+set%2E+Technical+Note+309%2C+SRI+International%2C+Menlo+Park%2C+CA%2E%2C+August%2E)
79. Warshall, Stephen. 1962. A theorem on boolean matrices. Journal of the ACM, 9(1):11–12, January. [↗](https://doi.org/10.1145/321105.321107)
80. Wintner, Shuly. 1991. Syntactic analysis of Hebrew sentences. Master’s thesis, Technion, Israel Institute of Technology, Haifa, Israel, July. (In Hebrew, abstract in English). [find](https://scholar.google.com/scholar?q=Wintner%2C+Shuly%2E+1991%2E+Syntactic+analysis+of+Hebrew+sentences%2E+Master%E2%80%99s+thesis%2C+Technion%2C+Israel+Institute+of+Technology%2C+Haifa%2C+Israel%2C+July%2E+%28In+Hebrew%2C+abstract+in+English%29%2E)
81. Wintner, Shuly. 1992. Syntactic analysis of Hebrew sentences using PATR. In Uzzi Ornan, Gideon Ariely, and Edit Doron, editors, Hebrew Computational Linguistics. Ministry of Science and Technology, chapter 4, pages 105–115. (In Hebrew). [find](https://scholar.google.com/scholar?q=Wintner%2C+Shuly%2E+1992%2E+Syntactic+analysis+of+Hebrew+sentences+using+PATR%2E+In+Uzzi+Ornan%2C+Gideon+Ariely%2C+and+Edit+Doron%2C+editors%2C+Hebrew+Computational+Linguistics%2E+Ministry+of+Science+and+Technology%2C+ch)
82. Wintner, Shuly and Nissim Francez. 1995a. An abstract machine for typed feature structures. In Proceedings of the 5th Workshop on Natural Language Understanding and Logic Programming, pages 205–220, Lisbon, May. [find](https://scholar.google.com/scholar?q=Wintner%2C+Shuly+and+Nissim+Francez%2E+1995a%2E+An+abstract+machine+for+typed+feature+structures%2E+In+Proceedings+of+the+5th+Workshop+on+Natural+Language+Understanding+and+Logic+Programming%2C+pages+205%E2%80%93220%2C+L)
83. Wintner, Shuly and Nissim Francez. 1995b. Parsing with typed feature structures. In Proceedings of the Fourth International Workshop on Parsing Technologies, pages 273–287, Prague, September. [↗](https://doi.org/10.48550/arxiv.cmp-lg/9601010)
84. Wintner, Shuly, Evgeniy Gabrilovich, and Nissim Francez, 1997. AMALIA – Abstract MAchine for LIinguistic Applications – User’s Guide. Laboratory for Computational Linguistics, Computer Science Deparmtent, Technion, Israel Institute of Technology, 32000 Haifa, Israel, January. [find](https://scholar.google.com/scholar?q=Wintner%2C+Shuly%2C+Evgeniy+Gabrilovich%2C+and+Nissim+Francez%2C+1997%2E+AMALIA+%E2%80%93+Abstract+MAchine+for+LIinguistic+Applications+%E2%80%93+User%E2%80%99s+Guide%2E+Laboratory+for+Computational+Linguistics%2C+Computer+Science+Deparmt)
85. Wintner, Shuly and Uzzi Ornan. 1991. Syntactic analysis of Hebrew sentences. In Proceedings of the 8th Israeli Symposium on Artificial Intelligence and Computer Vision, pages 201–230. Information Processing Association of Israel, December. [find](https://scholar.google.com/scholar?q=Wintner%2C+Shuly+and+Uzzi+Ornan%2E+1991%2E+Syntactic+analysis+of+Hebrew+sentences%2E+In+Proceedings+of+the+8th+Israeli+Symposium+on+Artificial+Intelligence+and+Computer+Vision%2C+pages+201%E2%80%93230%2E+Information+Proc)
86. Wintner, Shuly and Uzzi Ornan. 1996. Syntactic analysis of hebrew sentences. Natural Language Engineering, 1(3):261–288. [↗](https://doi.org/10.1017/s1351324900000206)
87. Yizhar, Dana. 1993. Computational grammar for Hebrew noun phrases. Master’s thesis, Computer Science Department, Hebrew University, Jerusalem, Israel, June. (In Hebrew). [find](https://scholar.google.com/scholar?q=Yizhar%2C+Dana%2E+1993%2E+Computational+grammar+for+Hebrew+noun+phrases%2E+Master%E2%80%99s+thesis%2C+Computer+Science+Department%2C+Hebrew+University%2C+Jerusalem%2C+Israel%2C+June%2E+%28In+Hebrew%29%2E)
88. Zajac, Rémi. 1992. Inheritance and constraint-based grammar formalisms. Computational Linguistics, 18(2):159–182. [find](https://scholar.google.com/scholar?q=Zajac%2C+Re%CC%81mi%2E+1992%2E+Inheritance+and+constraint%2Dbased+grammar+formalisms%2E+Computational+Linguistics%2C+18%282%29%3A159%E2%80%93182%2E)

*Updated 1 November 2026*