Bottom-up and top-down tree transformations— a comparison
From MaRDI portal
Publication:4102764
DOI10.1007/BF01704020zbMath0335.68061OpenAlexW2150256214MaRDI QIDQ4102764
Publication date: 1975
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01704020
Trees (05C05) Formal languages and automata (68Q45) General topics in the theory of software (68N01)
Related Items
DECIDABILITY OF THE SHAPE PRESERVING PROPERTY OF BOTTOM-UP TREE TRANSDUCERS, Fair termination is decidable for ground systems, Recursively defined tree transductions, First-order logic on finite trees, The equivalence problem for letter-to-letter bottom-up tree transducers is solvable, Homomorphisms and inverse homomorphisms on graph-walking automata, How to decide functionality of compositions of top-down tree transducers, Transduction from trees to graphs through folding, A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices, Compositions of Weighted Extended Tree Transducers — The Unambiguous Case, Functionality of compositions of top-down tree transducers is decidable, Weighted bottom-up and top-down tree transformations are incomparable, Alphabetic and synchronized tree transducers, The component hierarchy of chain-free cooperating distributed regular tree grammars, Tree-based generation of languages of fractals, Classes of Tree Homomorphisms with Decidable Preservation of Regularity, The HOM Problem is EXPTIME-Complete, A pumping lemma for output languages of macro tree transducers, Bottom-up tree pushdown automata: Classification and connection with rewrite systems, Alternating tree automata, Crisp-determinization of weighted tree automata over strong bimonoids, An axiomatic approach to the Korenjak-Hopcroft algorithms, The translation power of top-down tree-to-graph transducers, Closure properties of linear context-free tree languages with an application to optimality theory, Pushdown machines for the macro tree transducer, Undecidable properties of deterministic top-down tree transducers, Polypodic codes, Defining syntax-directed translations by tree bimorphisms, High level tree transducers and iterated pushdown tree transducers, Equivalences and transformations of regular systems - applications to recursive program schemes and grammars, EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS, Compositions of deterministic bottom-up, top-down, and regular look-ahead tree transformations, A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead, Weighted tree automata and weighted logics, Compositions of tree series transformations, Hybrid tree automata and the yield theorem for constituent tree automata, Branching synchronization grammars with nested tables, Compositions with superlinear deterministic top-down tree transformations, Deaccumulation techniques for improving provability, Tree transducers, L systems, and two-way machines, A representation of trees by languages. II, Forward and backward application of symbolic tree transducers, Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms, Shape preserving top-down tree transducers., A hierarchy of deterministic top-down tree transformations, The formal power of one-visit attribute grammars, Attribute grammars and recursive program schemes. I. II, A complete rewriting system for a monoid of tree transformation classes, Morphismes et bimorphismes d'arbres, Extended Multi Bottom-Up Tree Transducers, The copying power of one-state tree transducers, Unnamed Item, Generalized automata on infinite trees and Muller-McNaughton's theorem, Behavioural equivalence for infinite systems — Partially decidable!, Superlinear deterministic top-down tree transducers, Decidability of equivalence for a class of non-deterministic tree transducers, 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, The use of tree transducers to compute translations between graph algebras, Alphabetic tree relations, An implementation of syntax directed functional programming on nested- stack machines, Multiple context-free tree grammars: lexicalization and characterization, Composition closure of linear extended top-down tree transducers, PROPERTIES OF QUASI-RELABELING TREE BIMORPHISMS, Variants of top-down tree transducers with look-ahead, Functional programs as compressed data, A Büchi-like theorem for weighted tree automata over multioperator monoids, Tree transducers with external functions, Pushdown tree automata, Equational tree transformations, Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations, Copying theorems, Top-down tree transducers with regular look-ahead, Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity, Surface tree languages and parallel derivation trees, Basic tree transducers, Tree-Series-to-Tree-Series Transformations, Intercalation lemmas for tree transducer languages, Augmented transition networks and their relation to tree transducers, IO and OI. I, IO and OI. II, A representation of trees by languages. I, On tree transducers for partial functions, Determinacy and rewriting of functional top-down and MSO tree transformations, A Survey on Decidable Equivalence Problems for Tree Transducers, Characterizations of recognizable weighted tree languages by logic and bimorphisms, A Kleene Theorem for Forest Languages, Le théorème de transversale rationnelle dans les langages d'arbres, Compositions of Tree-to-Tree Statistical Machine Translation Models, DECOMPOSITION OF WEIGHTED MULTIOPERATOR TREE AUTOMATA, Decidability of the finiteness of ranges of tree transductions, The equivalence of bottom-up and top-down tree-to-graph transducers, General varieties of tree languages, On the equivalence problem for letter-to-letter top-down tree transducers, Nondeterministic operations on finite relational structures, Equational Weighted Tree Transformations with Discounting, Survey: Weighted Extended Top-Down Tree Transducers Part III — Composition, LINKS, Equational weighted tree transformations, Top-down tree transducers with deterministic top-down look-ahead, A Single Movement Normal Form for Minimalist Grammars, Hierarchies of tree series transformations, Extended multi bottom-up tree transducers, Transductions of dags and trees, Three hierarchies of transducers, Conversion and parsing of tree transducers for syntactic pattern analysis, Linear deterministic multi bottom-up tree transducers, Macro tree transducers, attribute grammars, and MSO definable tree translations., Context-free series on trees, An effectively given initial semigroup, Modular tree transducers, A complete classification of deterministic root-to-frontier tree transformation classes, Recognizable tree-languages and nonlinear morphisms, Iterated relabeling tree transducers, Erratum to: ``Top-down tree transducers with regular look-ahead, Macro tree transducers, On two families of forests
Cites Work
