We sketch an axiomatic reformalization of Generalized Phrase StructureGrammar (GPSG) – a definition purely within the language ofmathematical logic of the theory GPSG embodies. While this treatment raisesa number of theoretical issues for GPSG, our focus is not thereformalization itself but rather the method we employ. The model-theoreticapproach it exemplifies can be seen as a natural step in the evolution ofconstraint-based theories from their grammar-based antecedents. One goal ofthis paper is to introduce this approach to a broader audience and todemonstrate (...) its application to an existing theory. As such, it joins agrowing literature of similar studies. Prior studies, however, have had anumber of weaknesses – they generally offer little in the way ofconcrete examples of the advantages the approach has to offer, theytypically ignore significant portions of the theories they address, and, byfully abstracting away from the notion of grammar mechanism, they largelyabandon the possibility of establishing meaningful complexity results. Thesecond goal of the paper is to address these issues. Our thrust is to sketchthe reformalization sufficiently to illustrate the way in which it capturesFeature Specification Defaults (FSDs) and the Exhaustive Constant PartialOrdering (ECPO) property. Our definition of FSDs is considerably simplifiedrelative to the original formalization and is free of the procedural flavorthat has led some to assume that FSDs are inherently dynamic. Our treatmentof ECPO uncovers a gap in its definition in the context of partialcategories that has heretofore gone unnoticed. We offer these as ademonstration of the kind of insight that a model-theoretic reinterpretationcan bring to an existing theory. Further, since these are the types ofproperties that prior studies in this genre have failed to address, FSDs andECPO provide a means for us to explore the limitations of these approachesand to offer ways of overcoming them. Finally, the logical framework weemploy has a well defined generative capacity – definability in thisframework characterizes strong context-freeness in a particular sense. Thus,despite being more abstract than its constraint-based predecessors, themodel-theoretic approach, as exemplified here, can offer stronger complexityresults than are typically available in the constraint-based framework. (shrink)

In transformational grammar the notion of a chain has been central ever since its introduction in the early 80's. However, an insightful theory of chains has hitherto been missing. This paper develops such a theory of chains. Though it is applicable to virtually all chains, we shall focus on movement-induced chains. It will become apparent that chains are far from innocuous. A proper formulation of the structures and algorithms involved is quite a demanding task. Furthermore, we shall show that it (...) is possible to define structures in which the notion of a chain coincides with that of a constituent, so that the notion of a chain becomes redundant, generally without making the theory more complicated. These structures avoid some of the problems that beset the standard structures (such as unbound traces created by remnant movement). (shrink)

This paper is about a special version of PDL, proposed by Marcus Kracht, for reasoning about sibling ordered trees. It has four basic programs corresponding to the child, parent, left- and right-sibling relations in such trees. The original motivation for this language is rooted in the field of model-theoretic syntax. Motivated by recent developments in the area of semi-structured data, and, especially, in the field of query languages for XML (eXtensible Markup Language) documents, we revisit the language. This renewed interest (...) comes with a special focus on complexity and expressivity aspects of the language, aspects that have so far largely been ignored. We survey and derive complexity results, and spend most of the paper on the most important open question concerning the language: what is its expressive power? We approach this question from two angles: Which first-order properties can be expressed? And which second-order properties? While we are still some way from definitive answers to these questions, we discuss two first-order fragments of the PDL language for ordered trees, and show how the language can be used to express some typical (second-order) problems, like the boolean circuit and the frontier problem. (shrink)