Paper: Linear Context-Free Rewriting Systems And Deterministic Tree-Walking Transducers

ACL ID P92-1018
Title Linear Context-Free Rewriting Systems And Deterministic Tree-Walking Transducers
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1992
Authors
  • David Weir (University of Sussex, East Sussex UK)

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.