## 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*^{2}_{K,P}. In defining such sets of trees in *L*^{2}_{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*^{2}_{K,P}. Moreover, we show that the sets of finite trees
definable in *L*^{2}_{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.