Generalized sequential machine maps

DOI10.1016/S0022-0000(70)80017-4zbMath0198.03303MaRDI QIDQ2540272

James W. Thatcher

Publication date: 1970

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

languages, automata, networks

Related Items

The translation power of top-down tree-to-graph transducers ⋮ Compositions of constant weighted extended tree transducers ⋮ Definability results for top-down tree transducers ⋮ Synthesized and inherited functions. A new computational model for syntax-directed semantics ⋮ Pushdown machines for the macro tree transducer ⋮ Decision Problems of Tree Transducers with Origin ⋮ Tree Transformations and Dependencies ⋮ Defining syntax-directed translations by tree bimorphisms ⋮ 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 ⋮ A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead ⋮ Compositions of tree series transformations ⋮ Applications of Weighted Automata in Natural Language Processing ⋮ Branching synchronization grammars with nested tables ⋮ Deaccumulation techniques for improving provability ⋮ Attribute grammars as tree transducers over cyclic representations of infinite trees and their descriptional composition ⋮ A Mechanized Theory of Regular Trees in Dependent Type Theory ⋮ The equivalence problem for letter-to-letter bottom-up tree transducers is solvable ⋮ Tree transducers, L systems, and two-way machines ⋮ Forward and backward application of symbolic tree transducers ⋮ Compositions with Constant Weighted Extended Tree Transducers ⋮ PURE AND O-SUBSTITUTION ⋮ Weighted iterated linear control ⋮ 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 ⋮ Interdependent translation schemes ⋮ Unnamed Item ⋮ Look-ahead removal for total deterministic top-down tree transducers ⋮ The formal power of one-visit attribute grammars ⋮ Semantic preserving translations ⋮ Recognizable formal power series on trees ⋮ A complete rewriting system for a monoid of tree transformation classes ⋮ Morphismes et bimorphismes d'arbres ⋮ Extended Multi Bottom-Up Tree Transducers ⋮ Systolic trees and systolic language recognition by tree automata ⋮ Unnamed Item ⋮ Surjectivity of functors on grammars ⋮ Decidability of equivalence for a class of non-deterministic tree transducers ⋮ Top-down tree transducers with two-way tree walking look-ahead ⋮ -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 ⋮ Bottom-up and top-down tree transformations— a comparison ⋮ Alphabetic tree relations ⋮ Composition closure of linear extended top-down tree transducers ⋮ PROPERTIES OF QUASI-RELABELING TREE BIMORPHISMS ⋮ Tree transducers with external functions ⋮ Natural state transformations ⋮ Cascades of tree-automata and computations in universal algebras ⋮ Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations ⋮ Solvability of equivalence problem for program machines ⋮ Tree adjunct grammars ⋮ Top-down tree transducers with regular look-ahead ⋮ 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 ⋮ The component hierarchy of chain-free cooperating distributed regular tree grammars ⋮ Tree-based generation of languages of fractals ⋮ IO and OI. I ⋮ IO and OI. II ⋮ On tree transducers for partial functions ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Pumping lemmas for term languages ⋮ Generalized \({}^{1,5}\) sequential machine maps ⋮ Fixed-point constructions in order-enriched categories ⋮ RELATING TREE SERIES TRANSDUCERS AND WEIGHTED TREE AUTOMATA ⋮ 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 ⋮ Hierarchies of tree series transformations ⋮ Locally testable languages ⋮ Extended multi bottom-up tree transducers ⋮ Transductions of dags and trees ⋮ Tree-based picture generation ⋮ Theory of formal grammars ⋮ Three hierarchies of transducers ⋮ Conversion and parsing of tree transducers for syntactic pattern analysis ⋮ Linear deterministic multi bottom-up tree transducers ⋮ 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 ⋮ Macro tree transducers ⋮ A pumping lemma for output languages of macro tree transducers

Uses Software

• ALGOL 60

Cites Work

• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Properties of syntax directed translations
• Generalized sequential machine maps
• Tree acceptors and some of their applications
• On the generative power of transformational grammars
• A syntax directed compiler for ALGOL 60
• Decision Problems of Finite Automata Design and Related Arithmetics
• Regular canonical systems
• Translations on a context free grammar
• Transformations and translations from the point of view of generalized finite automata theory
• Recognition and parsing of context-free languages in time n3
• Algebraic automata and context-free sets
• Generalized finite automata theory with an application to a decision problem of second-order logic
• 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
• Automata in general algebras
• The minimalization of tree automata
• Two Families of Languages Related to ALGOL
• On some transformations in context-free grammars and languages
• Mappings and grammars on trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item