References

This collection of references only scratches the surface of the relevant literature. A much more complete survey of the historical perspective on typed unification grammars and programs can be found in Carpenter (1992), and in subsequent papers in ACL, EACL, COLING, etc.

Aït-Kaci, H. (1991). The WAM: A (Real) Tutorial. MIT Press, Cambridge, Massachusetts.

The best available introduction to Prolog compiler technology, focusing on Warren's Abstract Machine for Prolog.

Aït-Kaci, H. (1986a). An algebraic semantics approach to the effective resolution of type equations. Theoretical Computer Science, 45:293-351.

Seminal work in sorted feature structures, based on Aït-Kaci's 1984 University of Pennsylvania dissertation. Focuses on general constraint resolution.

Aït-Kaci, H., and Nasr, R. (1986b). LOGIN: A logical programming language with built-in inheritance. Journal of Logic Programming, 3:187-215.

The first application of feature structures to logic programming. Includes sorted, but not typed feature structures. Also includes good details on the Martelli and Montanari (1984) unification algorithm applied to feature structures.

Aït-Kaci, H. (1984). A Lattice-Theoretic Approach to Computation based on a Calculus of Partially Ordered Type Structures. Univ. of Pennsylvania dissertation.

Aït-Kaci's introduction of sorted $\psi$-terms, which are like our feature structures only without the appropriateness conditions, inequations and extensionality. An appendix contains a coding of the Zebra Puzzle, a benchmark logic puzzle for constraint resolution.

Carpenter, B. (1992) The Logic of Typed Feature Structures. Cambridge Tracts in Theoretical Computer Science 32, Cambridge University Press, New York.

Contains all the theoretical details behind the ALE feature structures, description language and applications. A must for fully understanding ALE and a number of related variations.

Carpenter, B. and G. Penn (1996) Compiling Typed Attribute-Value Logic Grammars. In H. Bunt and M. Tomita, eds., Recent Advances in Parsing Technology. Kluwer.

A description of the theoretical underpinnings of ALE 2.0, including the data structures, type inference mechanism, description resolution, parsing, and inequation solving.

Colmerauer, A. (1987). Theoretical model of prolog II. In van Canegham, M., and Warren, D. H., editors, Logic Programming and its Application, 1-31. Ablex, Norwood, New Jersey.

Describes unification with cyclic terms and inequations in a logic programming environment.

Gazdar, G., and Mellish, C. S. (1989). Natural Language Processing in Prolog. Addison-Wesley, Reading, Massachusetts.

An introduction to computational linguistics using Prolog. Also contains a very general introduction to simple PATR-II phrase structure grammars, including simple implementations of unification and parsing algorithms. A version is also available using Lisp.

Höhfeld, M., and Smolka, G. (1988). Definite relations over constraint languages. LILOG-REPORT 53, IBM - Deutschland GmbH, Stuttgart.

Highly theoretical description of a constraint logic programming paradigm, including an application to feature structures similar to those used in LOGIN.

Jaffar, J. (1984). Efficient unification over infinite terms. New Generation Computing, 2:207-219.

Unification algorithm for possibly cyclic terms in Prolog II. Includes quasi-linear complexity analysis.

Kasper, R. T., and Rounds, W. C. (1990). The logic of unification in grammar. Linguistics and Philosophy, 13(1):35-58.

The details of Kasper and Rounds original feature structure description system and related theorems.

Martelli, A., and Montanari, U. (1982). An efficient unification algorithm. ACM Transactions on Programming Languages and Systems, 4(2):258-282.

The Union/Find unification algorithm used by ALE, which was adapted to the cyclic case by Jaffar (1984).

Mastroianni, M. (1993) Attribute-Logic Phonology. Carnegie Mellon University Laboratory for Computational Linguistics Technical Report CMU-LCL-93-4. Pittsburgh.

The description and motivation for an attribute-logic approach to phonology. Includes extensive discussion of its implementation in ALE, including syllable structure and morphologically conditioned effects such as epenthesis, harmony and assimilation.

O'Keefe, R. A. (1990) The Craft of Prolog. MIT Press, Cambridge, Massachussetts.

Best text on advanced programming techniques using Prolog compilers. Should read Sterling and Shapiro's introduction as a pre-requisite.

Penn, G. (1993). A Utility for Typed Feature Structure-based Grammatical Theories. Technical Report. Laboratory for Computational Linguistics, Carnegie Mellon University, Pittsburgh.

This project served as the basis of the version 2.0 updates of ALE. The report details these updates, including the algorithms used to implement them and other efficiency issues. It also describes Penn's implementation of Head-Driven Phrase Structure Grammar (HPSG), as represented in the first eight chapters of (Pollard and Sag 1994).

Penn, G. (1999). A Parsing Algorithm to Reduce Copying in Prolog. Arbeitspapier des Sonderforschungsbereichs 340, Nr. 137.

A presentation of the Empty-First-Daughter closure algorithm, which can be used to reduce copying in Prolog-based parsers.

Penn, G., and Carpenter, B. (1993). Three Sources of Disjunction in a Typed Feature Structure-based Resolution System. Feature Formalisms and Linguistic Ambiguity, H. Trost ed. Ellis Horwood, New York.

A presentation of the principal sources of complexity in solving constraint puzzles, such as the Zebra Puzzle, a simplified version of which is presented in this manual; and an outline of steps taken to cope with them in the reversible general constraint resolver which was the precursor to ALE.

Penn, G. and Popescu, O. (1997). Head-Driven Generation and Indexing in ALE. Proceedings of Workshop on Computational Environments for Grammar Development and Linguistic Engineering (ENVGRAM), 35th ACL / 8th EACL.

Describes the implementation of ALE's head-driven generator, and a simple indexing strategy for lexical entries during generation.

Popescu, O. (1996). Head-Driven Generation for Typed Feature Structures. Carnegie Mellon University MS Project.

The extension of semantic-head-driven generation to typed feature structures used in ALE.

Pereira, F. C. N., and Shieber, S. M. (1987). Prolog and Natural-Language Analysis. Volume 10 of CSLI Lecture Notes. Center for the Study of Language and Information, Stanford.

Excellent introduction to the use of term unification grammars in natural language. Includes a survey of Prolog, parsing algorithms and many sample grammar applications in syntax and semantics.

Pollard, C. J. (in press). Sorts in unification-based grammar and what they mean. In Pinkal, M., and Gregor, B., editors, Unification in Natural Language Analysis. MIT Press, Cambridge, Massachusetts.

Contains the original extension of Rounds and Kasper's logical language to sorts. Also motivates the use of sorts in natural language grammars.

Pollard, C. J., and Sag, I. A. (1994). Head-driven Phrase Structure Grammar. Chicago University Press, Chicago.

The primary grammar formalism which motivated the construction of the ALE system. Provides many examples of how typed feature structures and their descriptions are employed in a sophisticated natural language application.

Shieber, S. M. (1986). An Introduction to Unification-Based Approaches to Grammar. Volume 4 of CSLI Lecture Notes. Center for the Study of Language and Information, Stanford.

Best source for getting acquainted with the application of feature structures and their descriptions to natural language grammars.

Shieber, S. M., Uszkoreit, H., Pereira, F. C. N., Robinson, J., and Tyson, M. (1983). The formalism and implementation of PATR-II. In Research on Interactive Acquisition and Use of Knowledge. Volume 1894 of SRI Final Report, SRI International, Menlo Park, California.

Original document describing the PATR-II formalism.

Shieber, S. M., Pereira, C. N., van Noord, G., Moore, R. C. (1990). Semantic-Head-Driven Generation. In Computational Linguistics, Vol. 16(1):30-42.

The main reference for a description of the semantic- head-driven generation algorithm.

Smolka, G. (1988a). A feature logic with subsorts. LILOG-REPORT 33, IBM - Deutschland GmbH, Stuttgart.

An alternative logic to that of Rounds and Kasper, which includes sorts, variables and general negation.

Smolka, G. (1988b). Logic programming with polymorphically order-sorted types. LILOG-REPORT 55, IBM - Deutschland GmbH, Stuttgart.

An application of ordered term unification to typed logic programming.

Sterling, L., and Shapiro, E. Y. (1986). The Art of Prolog: Advanced Programming Techniques. MIT Press, Cambridge, Massachusetts.

Best general introduction to logic programming in Prolog.

van Noord, G. (1989). BUG: A Directed Bottom-Up Generator for Unification Based Formalisms. Working Papers in Natural Language Processing, Katholieke Universiteit Leuven, Stichting Taaltechnologie Utrecht.

Proposes the first semantic-head-driven generation algorithm.