Tree transducers, L systems, and two-way machines

DOI10.1016/0022-0000(80)90058-6MaRDI QIDQ1136239zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

L systemsmacro grammarstop-down tree transducersETOL systemschecking machineschecking tree pushdown transducergeneralized syntax-directed translationtwo-way transducers

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(60)

• Compositions of extended top-down tree transducers
• The power of two-way deterministic checking stack automata
• Parameter Reduction in Grammar-Compressed Trees
• Top-down tree transducers with two-way tree walking look-ahead
• Look-ahead removal for total deterministic top-down tree transducers
• The OI-hierarchy is closed under control
• Macro tree transducers
• High level tree transducers and iterated pushdown tree transducers
• The generating power of total deterministic tree transducers
• The string generating power of context-free hypergraph grammars
• Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey
• Parameter reduction and automata evaluation for grammar-compressed trees
• Undecidable properties of deterministic top-down tree transducers
• 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
• Automata for XML -- a survey
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Multiple context-free tree grammars: lexicalization and characterization
• Concatenation of graphs
• Streaming ranked-tree-to-string transducers
• Basic tree transducers
• Linear deterministic multi bottom-up tree transducers
• The power of weighted regularity-preserving multi bottom-up 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
• Determinacy and rewriting of functional top-down and MSO tree transformations
• Word-mappings of level 2
• Branching synchronization grammars with nested tables
• Decision problems of tree transducers with origin
• The copying power of one-state tree transducers
• The equivalence problem for deterministic MSO tree transducers is decidable
• Functionality of compositions of top-down tree transducers is decidable
• 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
• Tree-based generation of languages of fractals
• Iterated stack automata and complexity classes
• Alternating tree automata
• Hierarchies of tree series transformations
• The generative power of delegation networks
• Tree-stack automata
• Tree-based picture generation
• Global storage cells for attributes in an attribute grammar
• The translation power of top-down tree-to-graph transducers
• Descriptional complexity of input-driven pushdown automata
• 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
• Hierarchies of hyper-AFLs
• Decision problems of tree transducers with origin
• Three hierarchies of transducers
• 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
• Deterministic top-down tree transducers with iterated look-ahead
• A pumping lemma for output languages of macro tree transducers
• 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)