Tree transducers, L systems, and two-way machines
From MaRDI portal
Publication:1136239
DOI10.1016/0022-0000(80)90058-6zbMATH Open0426.68075OpenAlexW2087945397MaRDI QIDQ1136239FDOQ1136239
Authors: Joost Engelfriet, Grzegorz Rozenberg, 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
L systemsmacro grammarstop-down tree transducersETOL systemschecking machineschecking tree pushdown transducergeneralized syntax-directed translationtwo-way transducers
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45)
Cites Work
- Bottom-up and top-down tree transformations— a comparison
- Top-down tree transducers with regular look-ahead
- IO and OI. II
- Properties of syntax directed translations
- Title not available (Why is that?)
- Syntax directed translations and the pushdown assembler
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Translations on a context free grammar
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
- Generalized sequential machine maps
- Mappings and grammars on trees
- Title not available (Why is that?)
- Composition of top-down and bottom-up tree transductions
- Simple matrix languages
- Full AFLs and nested iterated substitution
- Three hierarchies of transducers
- Title not available (Why is that?)
- Stack Machines and Classes of Nonnested Macro Languages
- Extended macro grammars and stack controlled machines
- A geometric hierarchy of languages
- Control sets on context-free grammar forms
- One way finite visit automata
- Checking automata and one-way stack languages
- Extension of tabled 0L-systems and languages
- Control sets on linear grammars
- Copying theorems
- Surface tree languages and parallel derivation trees
- Finite-turn checking automata
- Substitutions dans les EDT0L systèmes ultralinéaires
- Title not available (Why is that?)
- Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
- Tree transducers and tree languages
- Syntactic operators on full semiAFLs
- Intercalation lemmas for tree transducer languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- AFL with the semilinear property
- On equal matrix languages
- On some families of languages related to developmental systems
- Hypergrammars: An extension of macrogrammars
- A characterization of two-way deterministic classes of languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Controlled iteration grammars and full hyper-AFL's
- Controlled pushdown automata
- Absolutely parallel grammars and two-way finite-state transducers
- TOL schemes and control sets
- Bounded-crossing transducers
- Two-way sequential transductions and stack automata
- On recursion in ETOL systems
- On ETOL systems with rank
- Two-way A-transducers and AFL
- Iterated deterministic-substitution
- Title not available (Why is that?)
- Title not available (Why is that?)
- On ETOL systems of finite index
- Title not available (Why is that?)
Cited In (60)
- Streaming ranked-tree-to-string transducers
- Concatenation of graphs
- The power of weighted regularity-preserving multi bottom-up tree transducers
- Functionality of compositions of top-down tree transducers is decidable
- Compositions of extended top-down tree transducers
- Parameter Reduction in Grammar-Compressed Trees
- The power of two-way deterministic checking stack automata
- Look-ahead removal for total deterministic top-down tree transducers
- The OI-hierarchy is closed under control
- Top-down tree transducers with two-way tree walking look-ahead
- Macro tree transducers
- High level tree transducers and iterated pushdown tree transducers
- The generating power of total deterministic tree transducers
- Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey
- The string generating power of context-free hypergraph grammars
- Undecidable properties of deterministic top-down tree transducers
- Parameter reduction and automata evaluation for grammar-compressed trees
- Trading independent for synchronized parallelism in finite copying parallel rewriting systems
- The equivalence of bottom-up and top-down tree-to-graph transducers
- Context-free grammars with linked nonterminals
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Automata for XML -- a survey
- Multiple context-free tree grammars: lexicalization and characterization
- Linear deterministic multi bottom-up tree transducers
- Basic tree transducers
- Monadic second-order definable graph transductions: a survey
- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- Word-mappings of level 2
- Determinacy and rewriting of functional top-down and MSO tree transformations
- Decision problems of tree transducers with origin
- Branching synchronization grammars with nested tables
- The copying power of one-state tree transducers
- The equivalence problem for deterministic MSO tree transducers is decidable
- Tree-based generation of languages of fractals
- Deciding equivalence of top-down XML transformations in polynomial time
- Pushdown machines for the macro tree transducer
- Extended multi bottom-up tree transducers
- A comparison of boundary graph grammars and context-free hypergraph grammars
- Iterated stack automata and complexity classes
- Alternating tree automata
- Hierarchies of tree series transformations
- Tree-stack automata
- The generative power of delegation networks
- Tree-based picture generation
- Global storage cells for attributes in an attribute grammar
- Descriptional complexity of input-driven pushdown automata
- The translation power of top-down tree-to-graph transducers
- Output string languages of compositions of deterministic macro tree transducers
- Iterated linear control and iterated one-turn pushdowns
- Yield-languages of two-way pushdown tree automata
- Three hierarchies of transducers
- Decision problems of tree transducers with origin
- Hierarchies of hyper-AFLs
- Independent parallelism in finite copying parallel rewriting systems
- A survey on decidable equivalence problems for tree transducers
- Balancedness of MSO transductions in polynomial time
- Transductions of dags and trees
- A pumping lemma for output languages of macro tree transducers
- Deterministic top-down tree transducers with iterated look-ahead
- Functional programs as compressed data
This page was built for publication: Tree transducers, L systems, and two-way machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1136239)
