The descriptive complexity of generalized local sets
James Rogers · 1999
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, f...