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 systemsmacro grammarstop-down tree transducersETOL systemschecking machineschecking tree pushdown transducergeneralized syntax-directed translationtwo-way transducers

Mathematics Subject Classification ID

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

Related Items (60)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Syntactic operators on full semiAFLs
• Extended macro grammars and stack controlled machines
• On recursion in ETOL systems
• On ETOL systems with rank
• A geometric hierarchy of languages
• Two-way A-transducers and AFL
• Copying theorems
• Iterated deterministic-substitution
• Surface tree languages and parallel derivation trees
• Hypergrammars: An extension of macrogrammars
• Intercalation lemmas for tree transducer languages
• Control sets on context-free grammar forms
• One way finite visit automata
• IO and OI. II
• Controlled pushdown automata
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Checking automata and one-way stack languages
• Properties of syntax directed translations
• Syntax directed translations and the pushdown assembler
• Generalized sequential machine maps
• A characterization of two-way deterministic classes of languages
• Finite-turn checking automata
• AFL with the semilinear property
• Absolutely parallel grammars and two-way finite-state transducers
• Substitutions dans les EDT0L systèmes ultralinéaires
• Stack Machines and Classes of Nonnested Macro Languages
• Extension of tabled 0L-systems and languages
• On some families of languages related to developmental systems
• TOL schemes and control sets
• Bounded-crossing transducers
• Control sets on linear grammars
• Bottom-up and top-down tree transformations— a comparison
• Controlled iteration grammars and full hyper-AFL's
• Top-down tree transducers with regular look-ahead
• Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
• On ETOL systems of finite index
• Tree transducers and tree languages
• Composition of top-down and bottom-up tree transductions
• Three hierarchies of transducers
• Generalized finite automata theory with an application to a decision problem of second-order logic
• On equal matrix languages
• Full AFLs and nested iterated substitution
• Mappings and grammars on trees
• Simple matrix languages
• Two-way sequential transductions and stack automata
• Translations on a context free grammar

This page was built for publication: Tree transducers, L systems, and two-way machines