Computer Science – Computation and Language
Scientific paper
1995-05-23
Computer Science
Computation and Language
To appear in Specifying Syntactic Structures, papers from the Logic, Structures, and Syntax workshop, Amsterdam, Sept. 1994. L
Scientific paper
We introduce $L^2_{K,P}$, a monadic second-order language for reasoning about trees which characterizes the strongly Context-Free Languages in the sense that a set of finite trees is definable in $L^2_{K,P}$ iff it is (modulo a projection) a Local Set---the set of derivation trees generated by a CFG. This provides a flexible approach to establishing language-theoretic complexity results for formalisms that are based on systems of well-formedness constraints on trees. We demonstrate this technique by sketching two such results for Government and Binding Theory. First, we show that {\em free-indexation\/}, the mechanism assumed to mediate a variety of agreement and binding relationships in GB, is not definable in $L^2_{K,P}$ and therefore not enforcible by CFGs. Second, we show how, in spite of this limitation, a reasonably complete GB account of English can be defined in $L^2_{K,P}$. Consequently, the language licensed by that account is strongly context-free. We illustrate some of the issues involved in establishing this result by looking at the definition, in $L^2_{K,P}$, of chains. The limitations of this definition provide some insight into the types of natural linguistic principles that correspond to higher levels of language complexity. We close with some speculation on the possible significance of these results for generative linguistics.
No associations
LandOfFree
On Descriptive Complexity, Language Complexity, and GB does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Descriptive Complexity, Language Complexity, and GB, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Descriptive Complexity, Language Complexity, and GB will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-617224