Mappings and grammars on trees

DOI10.1007/BF01695769zbMath0203.30103MaRDI QIDQ5603192

William C. Rounds

Publication date: 1970

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Related Items

DECIDABILITY OF THE SHAPE PRESERVING PROPERTY OF BOTTOM-UP TREE TRANSDUCERS ⋮ Applications of Weighted Automata in Natural Language Processing ⋮ Unnamed Item ⋮ Compositions with Constant Weighted Extended Tree Transducers ⋮ How to decide functionality of compositions of top-down tree transducers ⋮ Unnamed Item ⋮ Compositions of Weighted Extended Tree Transducers — The Unambiguous Case ⋮ Definability Results for Top-Down Tree Transducers ⋮ Functionality of compositions of top-down tree transducers is decidable ⋮ Some results in tree automata ⋮ A hierarchy of deterministic top-down tree transformations ⋮ Regular Approximation of Weighted Linear Context-Free Tree Languages ⋮ Tree-stack automata ⋮ Superlinear deterministic top-down tree transducers ⋮ Bottom-up and top-down tree transformations— a comparison ⋮ On the complexity of finite, pushdown, and stack automata ⋮ Alphabetic and synchronized tree transducers ⋮ Cascades of tree-automata and computations in universal algebras ⋮ Top-down tree transducers with regular look-ahead ⋮ Unnamed Item ⋮ Tree-based generation of languages of fractals ⋮ Une Relation d'Equivalence Decidable sur la Classe des Forêts Reconnaissables ⋮ RELATING TREE SERIES TRANSDUCERS AND WEIGHTED TREE AUTOMATA ⋮ Characterizing Compatible View Updates in Syntactic Bidirectionalization ⋮ Transductions of dags and trees ⋮ Three hierarchies of transducers ⋮ Conversion and parsing of tree transducers for syntactic pattern analysis ⋮ A pumping lemma for output languages of macro tree transducers ⋮ Synchronized tree automata ⋮ The translation power of top-down tree-to-graph transducers ⋮ Compositions of constant weighted extended tree transducers ⋮ Definability results for top-down tree transducers ⋮ Closure properties of linear context-free tree languages with an application to optimality theory ⋮ Synthesized and inherited functions. A new computational model for syntax-directed semantics ⋮ Linearity and nondeletion on monadic context-free tree grammars ⋮ Pushdown machines for the macro tree transducer ⋮ Undecidable properties of deterministic top-down tree transducers ⋮ Decision Problems of Tree Transducers with Origin ⋮ Tree Transformations and Dependencies ⋮ High level tree transducers and iterated pushdown tree transducers ⋮ Decision problems of tree transducers with origin ⋮ EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS ⋮ Designing equivalent semantic models for process creation ⋮ A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead ⋮ Compositions of tree series transformations ⋮ Branching synchronization grammars with nested tables ⋮ Deterministic tree pushdown automata and monadic tree rewriting systems ⋮ Compositions with superlinear deterministic top-down tree transformations ⋮ Deaccumulation techniques for improving provability ⋮ Attribute grammars as tree transducers over cyclic representations of infinite trees and their descriptional composition ⋮ Tree transducers, L systems, and two-way machines ⋮ Forward and backward application of symbolic tree transducers ⋮ PURE AND O-SUBSTITUTION ⋮ Weighted iterated linear control ⋮ Shape preserving top-down tree transducers. ⋮ Interdependent translation schemes ⋮ Look-ahead removal for total deterministic top-down tree transducers ⋮ The formal power of one-visit attribute grammars ⋮ From Tree-Based Generators to Delegation Networks ⋮ A complete rewriting system for a monoid of tree transformation classes ⋮ Morphismes et bimorphismes d'arbres ⋮ Extended Multi Bottom-Up Tree Transducers ⋮ Pebble machines and tree walking machines ⋮ Systolic trees and systolic language recognition by tree automata ⋮ Yield-languages recognized by alternating tree recognizers ⋮ Unnamed Item ⋮ Multidimensional trees ⋮ Top-down tree transducers with two-way tree walking look-ahead ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ -Treeautomata and their relation to weighted context-free grammars ⋮ Deterministic top-down tree transducers with iterated look-ahead ⋮ Compositions of extended top-down tree transducers ⋮ 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 ⋮ Tree transducers with external functions ⋮ Pushdown tree automata ⋮ Second-order abstract categorial grammars as hyperedge replacement grammars ⋮ On procedures as open subroutines. II ⋮ Natural state transformations ⋮ Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations ⋮ Tree adjunct grammars ⋮ Composing stack-attributed tree transducers ⋮ Un théorème de duplication pour les forets algébriques ⋮ 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 ⋮ A generalized approach to formal languages ⋮ Linear context-free tree languages and inverse homomorphisms ⋮ Un théorème de Chomsky-Schützenberger pour les forets algébriques ⋮ IO and OI. I ⋮ IO and OI. II ⋮ On tree transducers for partial functions ⋮ Classes of formal grammars ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Pumping lemmas for term languages ⋮ Le théorème de transversale rationnelle dans les langages d'arbres ⋮ Deciding equivalence of top-down XML transformations in polynomial time ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ The equivalence of bottom-up and top-down tree-to-graph transducers ⋮ Generalized sequential machine maps ⋮ On the equivalence problem for letter-to-letter top-down tree transducers ⋮ Survey: Weighted Extended Top-Down Tree Transducers Part III — Composition ⋮ Regular Approximation of Weighted Linear Nondeleting Context-Free Tree Languages ⋮ The generating power of total deterministic tree transducers ⋮ Top-down tree transducers with deterministic top-down look-ahead ⋮ On the Mild Context-Sensitivity of k-Tree Wrapping Grammar ⋮ Hierarchies of tree series transformations ⋮ Extended multi bottom-up tree transducers ⋮ Rational languages defined with a non-associative concatenation ⋮ Tree-based picture generation ⋮ Linear deterministic multi bottom-up tree transducers ⋮ Tree pushdown automata ⋮ The complexity of the exponential output size problem for top-down and bottom-up tree transducers ⋮ Modular tree transducers ⋮ A complete classification of deterministic root-to-frontier tree transformation classes ⋮ Iterated relabeling tree transducers ⋮ Decidability of EDT0L structural equivalence ⋮ Output string languages of compositions of deterministic macro tree transducers ⋮ Macro tree transducers ⋮ On two families of forests ⋮ wMSO theories as grammar formalisms

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Tree acceptors and some of their applications
• A syntax directed compiler for ALGOL 60
• Translations on a context free grammar
• Transformations and translations from the point of view of generalized finite automata theory
• Algebraic automata and context-free sets
• Syntax-Directed Transduction
• Algebra automata I: Parallel programming as a prolegomena to the categorical approach
• Tree generating regular systems
• Indexed Grammars—An Extension of Context-Free Grammars
• The minimalization of tree automata
• Generalized finite automata theory with an application to a decision problem of second-order logic