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
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
