Three hierarchies of transducers
From MaRDI portal
Publication:4747534
DOI10.1007/BF01786975zbMath0509.68078OpenAlexW2146106361MaRDI QIDQ4747534
Publication date: 1982
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01786975
Related Items (33)
High level tree transducers and iterated pushdown tree transducers ⋮ The OI-hierarchy is closed under control ⋮ Branching synchronization grammars with nested tables ⋮ Compositions with superlinear deterministic top-down tree transformations ⋮ Tree transducers, L systems, and two-way machines ⋮ MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS ⋮ How to decide functionality of compositions of top-down tree transducers ⋮ Functionality of compositions of top-down tree transducers is decidable ⋮ Weighted bottom-up and top-down tree transformations are incomparable ⋮ The IO- and OI-hierarchies ⋮ A complete rewriting system for a monoid of tree transformation classes ⋮ The copying power of one-state tree transducers ⋮ Superlinear deterministic top-down tree transducers ⋮ Iterated stack automata and complexity classes ⋮ Top-down tree transducers with two-way tree walking look-ahead ⋮ Transducer-based analysis of cryptographic protocols ⋮ Deterministic top-down tree transducers with iterated look-ahead ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Composition closure of linear extended top-down tree transducers ⋮ Alphabetic and synchronized tree transducers ⋮ Basic tree transducers ⋮ Tree-based generation of languages of fractals ⋮ Two-way pebble transducers for partial functions and their composition ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ The generating power of total deterministic tree transducers ⋮ Hierarchies of tree series transformations ⋮ Hierarchies of hyper-AFLs ⋮ Macro tree transducers, attribute grammars, and MSO definable tree translations. ⋮ The complexity of the exponential output size problem for top-down and bottom-up tree transducers ⋮ A complete classification of deterministic root-to-frontier tree transformation classes ⋮ Output string languages of compositions of deterministic macro tree transducers ⋮ Macro tree transducers ⋮ Algebraic aspects of families of fuzzy languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Syntactic operators on full semiAFLs
- Tree transducers, L systems, and two-way machines
- Two-way A-transducers and AFL
- On derivation trees of indexed grammars - an extension of the uvwxy- theorem
- Copying theorems
- Surface tree languages and parallel derivation trees
- Intercalation lemmas for tree transducer languages
- One way finite visit automata
- On tree transducers for partial functions
- Hierarchy theorems for two-way finite state transducers
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
- Generalized sequential machine maps
- A characterization of two-way deterministic classes of languages
- Absolutely parallel grammars and two-way finite-state transducers
- Stack Machines and Classes of Nonnested Macro Languages
- Extension of tabled 0L-systems and languages
- Decomposition Theorems for Various Kinds of Languages Parallel in Nature
- 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
- Tree transducers and tree languages
- Composition of top-down and bottom-up tree transductions
- A general theory of translation
- Indexed Grammars—An Extension of Context-Free Grammars
- Chains of full AFL's
- Mappings and grammars on trees
- Two-way sequential transductions and stack automata
- Translations on a context free grammar
This page was built for publication: Three hierarchies of transducers
