Tree transducers, L systems, and two-way machines

DOI10.1016/0022-0000(80)90058-6zbMath0426.68075OpenAlexW2087945397MaRDI QIDQ1136239

Grzegorz Rozenberg, Joost Engelfriet, Giora Slutzki

Publication date: 1980

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/tree-transducers-l-systems-and-twoway-machines(b76e9957-faa8-428c-a733-850384551c4d).html

zbMATH Keywords

L systems macro grammars top-down tree transducers ETOL systems checking machines checking tree pushdown transducer generalized syntax-directed translation two-way transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items

Monadic second-order definable graph transductions: a survey, Alternating tree automata, The translation power of top-down tree-to-graph transducers, Descriptional Complexity of Input-Driven Pushdown Automata, Pushdown machines for the macro tree transducer, Undecidable properties of deterministic top-down tree transducers, Decision Problems of Tree Transducers with Origin, High level tree transducers and iterated pushdown tree transducers, The equivalence problem for deterministic MSO tree transducers is decidable, Decision problems of tree transducers with origin, Yield-languages of two-way pushdown tree automata, The OI-hierarchy is closed under control, Branching synchronization grammars with nested tables, Automata for XML -- a survey, The generative power of delegation networks, Iterated linear control and iterated one-turn pushdowns, Functionality of compositions of top-down tree transducers is decidable, Look-ahead removal for total deterministic top-down tree transducers, Balancedness of MSO transductions in polynomial time, Parameter reduction and automata evaluation for grammar-compressed trees, Word-mappings of level 2, A comparison of boundary graph grammars and context-free hypergraph grammars, Tree-stack automata, Independent parallelism in finite copying parallel rewriting systems, The copying power of one-state tree transducers, The string generating power of context-free hypergraph grammars, Iterated stack automata and complexity classes, Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey, Top-down tree transducers with two-way tree walking look-ahead, Deterministic top-down tree transducers with iterated look-ahead, Compositions of extended top-down tree transducers, Concatenation of graphs, Multiple context-free tree grammars: lexicalization and characterization, Functional programs as compressed data, The Power of Weighted Regularity-Preserving Multi Bottom-Up Tree Transducers, Basic tree transducers, Tree-based generation of languages of fractals, Determinacy and rewriting of functional top-down and MSO tree transformations, A Survey on Decidable Equivalence Problems for Tree Transducers, Parameter Reduction in Grammar-Compressed Trees, Streaming ranked-tree-to-string transducers, The power of two-way deterministic checking stack automata, Trading independent for synchronized parallelism in finite copying parallel rewriting systems, Deciding equivalence of top-down XML transformations in polynomial time, The equivalence of bottom-up and top-down tree-to-graph transducers, Global storage cells for attributes in an attribute grammar, CONTEXT-FREE GRAMMARS WITH LINKED NONTERMINALS, The generating power of total deterministic tree transducers, Hierarchies of tree series transformations, Extended multi bottom-up tree transducers, Transductions of dags and trees, A comparison of tree transductions defined by monadic second order logic and by attribute grammars, Tree-based picture generation, Three hierarchies of transducers, Linear deterministic multi bottom-up tree transducers, Hierarchies of hyper-AFLs, Macro tree transducers, attribute grammars, and MSO definable tree translations., Output string languages of compositions of deterministic macro tree transducers, Macro tree transducers, A pumping lemma for output languages of macro tree transducers

Cites Work