Some formal properties of stratified feature grammars

Abstract

In this paper, we investigate the formal expressive properties of Stratified Feature Grammar (SFG), a new logic-based linguistic framework motivated by relational grammar and metagraph grammar, as well as by Kasper-Rounds logic. The driving force behind SFG is the generalization of the concept feature from an unanalyzable atomic one to a sequence of so-called R-signs. The linguistic interpretation of these stratified features is that each R-sign in such a sequence denotes a primitive grammatical relation such as subject or direct object in different syntactic "strata". This generalization permits the specification of a rigorous feature-structure-based formalism for natural-language grammars based on the view that syntax is "multistratal" and "relational". The introduction of stratified features leads to several other innovations, two of which might have utility in other frameworks. One is the idea of imposing a partial order on features. The other is the concept of (data) justification: essentially, this is a stipulation that for an S-graph to be well-formed with respect to some grammar G it must, in addition to satisfying the rules of G, have each of its "core" data (each feature occurrence, each node-label occurrence and each instance of so-called structure-sharing) justified in a formally precise manner by some rule of Justification ensures that. Justification ensures that satisfying S-graphs do not have more structure than absolutely necessary and so makes it appealing to a notion of "minimal model" otiose. Justification plays a key role in a number of our proofs. The formal results presented here include the following. First, it is proved that in the unrestricted SFG framework, every type 0 (r.e.) language is generated by some SFG. Then, we restrict the framework to so-called bounded SFG with two linguistically motivated principles: Lexical Anchoring and Boundedness. Anchoring requires, in essence, that each core datum of an S-graph be justified by a word in its yield. Boundedness insures that S-graph features are short. Although these restrictions together put the class of bounded SFG languages well within the class of recursive languages, we go on to demonstrate that the recognition problem for bounded SFG is NP-hard. Further, we establish that a bounded SFG language need not be semi-linear. On the matter of upper bounds, we show that every bounded SFL can be recognized by a nondeterministic Turing machine in n log n space and polynomial time and that the recognition problem for bounded SFL's is NP-complete. © 1993 J.C. Baltzer AG, Science Publishers.