Linear Context-Free Rewriting Systems and Deterministic Tree-Walking Transducers

Linear Context-Free Rewriting Systems and Deterministic Tree-Walking Transducers* David J. Weir School of Cognitive and Computing Sciences University of Sussex Falmer, Brighton BN1 9QH davidw @ cogs. sussex, ac. uk Abstract We show that the class of string languages gener- ated by linear context-free rewriting systems is equal to the class of output languages of deterministic tree- walking transducers. From equivalences that have pre- viously been established we know that this class of lan- guages is also equal to the string languages generated by context-free hypergraph grammars, multicompo- nent tree-adjoining grammars, and multiple context- free grammars and to the class of yields of images of the regular tree languages under finite-copying top- down tree transducers. Introduction In [9] a comparison was made of the generative capac- ity of a number of grammar formalisms. Several were found to share a number of characteristics (described below) and the class of such formalisms was called lin- ear context-free rewriting systems. This paper shows how the class of string languages generated by linear context-free rewriting systems relates to a number of other systems that have been studied by formal lan- guage theorists. In particular, we show that the class of string languages generated by linear context-free rewriting systems is equal to the class of output lan- guages of deterministic tree-walking transducers [1]. A number of other equivalences have already been established. In [10] it was shown that linear context- free rewriting systems and multicomponent tree ad- joining grammars [6] generate the same string lan- guages. The multiple context-free grammars of [7] are equivalent to linear context-free systems. This follows *I would like to thank Joost Engelfriet for drawing my attention to context-free hypergraph grammars and their relationship to deterministic tree-walking automata. from the fact that multiple context-free grammars are exactly that subclass of the linear context-free rewrit- ing systems in which the objects generated by the grammar are tuples of strings. The class of output languages of deterministic tree-walking transducers is known to be equal to the class of yields of images of the regular tree languages under finite-copying top-down tree transducers [4] and in [3] it was shown that it also equal to the string languages generated by context-free hypergraph grammars [2, 5]. We therefore have a number of Characterizations of the same class of languages and results that have been established for the class of languages associated with one system carry over to the others. This is particu- larly fruitful in this case since the output languages of deterministic tree-walking transducers have been well studied (see [4]). In the remainder of the paper we describe linear context-free rewriting systems and deterministic tree- walking transducers and outline the equivalence proof. We then describe context-free hypergraph grammars and observe that they are a context-free rewriting sys- tem. Linear Context-Free Rewriting Systems Linear context-free rewriting systems arose from the observation that a number of grammatical formalisms share two properties. 1. Their derivation tree sets can be generated by a context-free grammar. 2. Their composition operations …

Content truncated to 500 words