SFB 340, Bericht Nr. 84

J. Rogers

The Descriptive Complexity of Generalized Local Sets

Arbeitspapiere des SFB 340, Bericht Nr. 84 (1997), 20pp.
DVI (77kb); Postscript (333b)1-up; Postscript gzip-komprimiert (86kb) 1-up , 2-up.

Abstract

Context-free grammars and tree automata, because they are required to be finite, are limited to defining sets of trees in which the branching is bounded by a finite constant. As a result they cannot capture accounts of syntactic phenomena in which no such a priori bound exists - in flat accounts of coordination, for instance. This mismatch led Langendoen in 1976 and Gazdar, et al., in 1985 (GPSG) to propose varieties of two level grammars, in the one case infinite grammars that are themselves generated by other grammars, in the other grammars that permit regular expressions on the right-hand side of rewrite rules. In earlier work, we have characterized the local sets (the sets of trees generated by CFGs) and the recognizable sets (those accepted by tree automata) by definability in the logical language L²_K,P. In defining such sets of trees in L²_K,P, however, one must explicitly bound the branching. In this paper we explore the consequences of relaxing these bounds. We show, for instance, that the GPSG account of coordination can be captured in L²_K,P. Moreover, we show that the sets of finite trees definable in L²_K,P without the bound are exactly the sets of trees accepted by tree automata that are representable as regular sets, or, equivalently, projections of sets of trees generated by infinite CFGs that are themselves generated by regular grammars.