Sets out the basic theory of normal modal and temporal propositional logics; applies this theory to logics of discrete (integer), dense (rational), and continuous (real) time, to the temporal logic of henceforth, next, and until, and to the propositional dynamic logic of regular programs.

Barriers is Linguistic Inquiry Monograph 13.

Many of the formalisms used in Attribute Value grammar are notational variants of languages of propositional modal logic, and testing whether two Attribute Value Structures unify amounts to testing for modal satisfiability. In this paper we put this observation to work. We study the complexity of the satisfiability problem for nine modal languages which mirror different aspects of AVS description formalisms, including the ability to express re-entrancy, the ability to express generalisations, and the ability to express recursive constraints. Two main (...) techniques are used: either Kripke models with desirable properties are constructed, or modalities are used to simulate fragments of Propositional Dynamic Logic. Further possibilities for the application of modal logic in computational linguistics are noted. (shrink)

Feature logics are the logical basis for so-called unification grammars studied in computational linguistics. We investigate the expressivity of feature terms with negation and the functional uncertainty construct needed for the description of long-distance dependencies and obtain the following results: satisfiability of feature terms is undecidable, sort equations can be internalized, consistency of sort equations is decidable if there is at least one atom, and consistency of sort equations is undecidable if there is no atom.

By formalizing recent syntactic theories for natural languages Stabler shows how their complexity can be handled without guesswork or oversimplification. By formalizing recent syntactic theories for natural languages in the tradition of Chomsky's Barriers, Stabler shows how their complexity can be handled without guesswork or oversimplification. He introduces logical representations of these theories together with special deductive techniques for exploring their consequences that will provide linguists with a valuable tool for deriving and testing theoretical predictions and for experimenting with alternative (...) formulations of grammatical principles. Stabler's novel approach allows results to be deduced with straightforward calculations and provides a systematic framework for tackling the problem of how speakers can infer the properties of an utterance from principles of the grammar. The special treatment of equality, induction principles, and inclusion of a general method for collecting structures from proofs means that sophisticated linguistic arguments can be carried out in detail, giving a rich perspective to issues in linguistic theory and parsing. (shrink)

We callsyntactic coding a technique which converts syntactic principles or constraints on representations into grammatical rules which can be implemented in any given rule grammar. In this paper we show that any principle or constraint on output trees formalizable in a certain fragment of dynamic logic over trees can be coded in this sense. This allows to reduce in a mechanical fashion most of the current theories of government and binding into GPSG-style grammars. This will be exemplified with Rizzi'sRelativized Minimality.