Tree acceptors and some of their applications

DOI10.1016/S0022-0000(70)80041-1zbMath0212.02901MaRDI QIDQ2544414

John Doner

Publication date: 1970

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

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70)

Related Items (only showing first 100 items - show all)

Monadic second-order definable graph transductions: a survey ⋮ Modulo-counting quantifiers over finite trees ⋮ Alternating tree automata ⋮ Reductions in tree replacement systems ⋮ A branching time logic with past operators ⋮ Closure properties of linear context-free tree languages with an application to optimality theory ⋮ Cooperating Distributed Tree Automata ⋮ Containment of Monadic Datalog Programs via Bounded Clique-Width ⋮ Tight lower bounds for query processing on streaming and external memory data ⋮ Defining syntax-directed translations by tree bimorphisms ⋮ Definable transductions and weighted logics for texts ⋮ Decidability of the minimization of fuzzy tree automata with membership values in complete lattices ⋮ Similarity-based minimization of fuzzy tree automata ⋮ Lower bounds on type checking overloading ⋮ The monadic second-order logic of graphs. I: Recognizable sets of finite graphs ⋮ A first-order axiomatization of the theory of finite trees ⋮ Monadic second-order definable text languages ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Weighted tree automata and weighted logics ⋮ The monadic second-order logic of graphs, II: Infinite graphs of bounded width ⋮ Algebraic properties of complete residuated lattice valued tree automata ⋮ Weighted tree automata with constraints ⋮ Hybrid tree automata and the yield theorem for constituent tree automata ⋮ Unnamed Item ⋮ Computability by monadic second-order logic ⋮ Automata for XML -- a survey ⋮ Logical description of context-free graph languages ⋮ Tree algebras and varieties of tree languages ⋮ Backward type inference for XML queries ⋮ Capturing MSO with One Quantifier ⋮ Cellular automata between sofic tree shifts ⋮ A representation of trees by languages. II ⋮ Forward and backward application of symbolic tree transducers ⋮ Automata Presenting Structures: A Survey of the Finite String Case ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Machines in a category ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Büchi context-free languages ⋮ Weighted logics for unranked tree automata ⋮ An algebraic definition for control structures ⋮ Research in the theory of inductive inference by GDR mathematicians - A survey ⋮ Coding tree languages based on lattice-valued logic ⋮ Tree acceptors and grammar forms ⋮ Unnamed Item ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ Dipole information complementarity in discrete 2D patterns. ⋮ The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability ⋮ A regular characterization of graph languages definable in monadic second-order logic ⋮ Generalized automata on infinite trees and Muller-McNaughton's theorem ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Weighted monadic Datalog ⋮ On the equivalence of recursive and nonrecursive Datalog programs ⋮ Finite automata on directed graphs ⋮ Compositions of extended top-down tree transducers ⋮ The monadic second-order logic of graphs. VII: Graphs as relational structures ⋮ Variable Tree Automata over Infinite Ranked Alphabets ⋮ Weighted automata and logics for infinite nested words ⋮ MONA IMPLEMENTATION SECRETS ⋮ On characterization of fuzzy tree pushdown automata ⋮ A Büchi-like theorem for weighted tree automata over multioperator monoids ⋮ Linear delay enumeration and monadic second-order logic ⋮ Algebraic recognizability of regular tree languages ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Decidable containment of recursive queries ⋮ Querying linguistic treebanks with monadic second-order logic in linear time ⋮ Mit regulären Grundbegriffen definierbare Prädikate ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ A generalized approach to formal languages ⋮ A representation of trees by languages. I ⋮ Structural pattern recognition, homomorphisms, and arrangements ⋮ Determinacy and rewriting of functional top-down and MSO tree transformations ⋮ A calculus of branching processes ⋮ Characterizations of recognizable weighted tree languages by logic and bimorphisms ⋮ An axiom system for the weak monadic second order theory of two successors ⋮ Computing with graph rewriting systems with priorities ⋮ Characterizing derivation trees of context-free grammars through a generalization of finite automata theory ⋮ Linear weighted tree automata with storage and inverse linear tree homomorphisms ⋮ On Finite and Polynomial Ambiguity of Weighted Tree Automata ⋮ Generalized sequential machine maps ⋮ Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics ⋮ Series-parallel languages and the bounded-width property ⋮ Automata on finite trees ⋮ Reasoning about XML constraints based on XML-to-relational mappings ⋮ Decidability and complexity of simultaneous rigid E-unification with one variable and related results ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ A characterization of Büchi tree automata ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Tree pushdown automata ⋮ Uniform and nonuniform recognizability. ⋮ Ordering constraints over feature trees expressed in second-order monadic logic. ⋮ Query automata over finite trees ⋮ Characterization of tree automata based on quantum logic ⋮ Characterizing weighted MSO for trees by branching transitive closure logics ⋮ A link between multioperator and tree valuation automata and logics ⋮ An operational and denotational approach to non-context-freeness ⋮ wMSO theories as grammar formalisms ⋮ Ambiguity hierarchies for weighted tree automata

Uses Software

• ALGOL 60

Cites Work

• Undecidable theories
• Finite state languages
• The first order properties of products of algebraic systems
• An application of games to the completeness problem for formalized theories
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Restricted Set-Theoretical Definitions in Arithmetic
• Operations Which Preserve Definability in Languages
• Two Families of Languages Related to ALGOL
• Decision methods in the theory of ordinals
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Tree acceptors and some of their applications