Constraint-based theories of grammar and grammar formalisms are becoming an increasingly widespread area of research in computational linguistics. Constraint-Based Grammar Formalisms provides the first rigorous mathematical and computational basisfor this important area. It introduces new applications to both natural and computer languages and brings together Stuart Shieber's many contributions that have been at the core of developments ranging from the discovery of improved explanations of linguistic phenomena such as binding and coordination to the detailed mathematical analysis of constraint-solving and parsing in a variety of grammar formalisms. This thorough examination of the theoretical and computational foundations of constraint-based grammars and applications to natural-language analysis is unique in several respects. Shieber's theoretical framework may be applied to a whole class of formalisms with properties that make it possible to define a general...