Generalized finite automata theory with an application to a decision problem of second-order logic

From MaRDI portal

Publication:5538923

Jump to:navigation, search

DOI10.1007/BF01691346zbMath0157.02201MaRDI QIDQ5538923

James W. Thatcher, Jesse B. Wright

Publication date: 1968

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

zbMATH Keywords

mathematical logic

Related Items

A Model-Theoretic Description of Tree Adjoining Grammars1 1The research presented in this paper was supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 441, TP A2. The authors wish to thank Jens Michaelis and Stephan Kepser for helpful comments. ⋮ Crisp-determinization of weighted tree automata over strong bimonoids ⋮ Feature automata and recognizable sets of feature trees ⋮ Closure properties of linear context-free tree languages with an application to optimality theory ⋮ Provenance Circuits for Trees and Treelike Instances ⋮ Containment of Monadic Datalog Programs via Bounded Clique-Width ⋮ Tight lower bounds for query processing on streaming and external memory data ⋮ First-order properties of trees, star-free expressions, and aperiodicity ⋮ Unnamed Item ⋮ A Logical Characterization of Timed Pushdown Languages ⋮ Computability by monadic second-order logic ⋮ Communicating Finite-State Machines and Two-Variable Logic ⋮ Deciding equivalence of finite tree automata ⋮ Capturing MSO with One Quantifier ⋮ First-order logic on finite trees ⋮ MSO definable text languages ⋮ Logics for unordered trees with data constraints ⋮ Unnamed Item ⋮ A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices ⋮ Unnamed Item ⋮ Solving the Weighted HOM-Problem With the Help of Unambiguity ⋮ Logics and Automata for Totally Ordered Trees ⋮ Verification of component-based systems with recursive architectures ⋮ Unnamed Item ⋮ Tree Automata with Global Constraints ⋮ Construction of Tree Automata from Regular Expressions ⋮ The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem ⋮ Unnamed Item ⋮ E-generalization using grammars ⋮ A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths ⋮ Variable Tree Automata over Infinite Ranked Alphabets ⋮ Unnamed Item ⋮ Pebble Weighted Automata and Weighted Logics ⋮ A Practical Approach to Courcelle's Theorem ⋮ Algebraic recognizability of regular tree languages ⋮ Logic, Languages, and Rules for Web Data Extraction and Reasoning over Data ⋮ Stack and locally finite transformations on structures with reversible transitions ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Characterizing CTL-like logics on finite trees. ⋮ Symbolic model checking with rich assertional languages ⋮ Monadic Second Order Logic on Graphs with Local Cardinality Constraints ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complementation of Branching Automata for Scattered and Countable N-Free Posets ⋮ Unnamed Item ⋮ Characterizing EF and EX tree logics ⋮ The component hierarchy of chain-free cooperating distributed regular tree grammars ⋮ Fly-Automata, Their Properties and Applications ⋮ Tree Automata over Infinite Alphabets ⋮ Incremental reasoning on monadic second-order logics with logic programming ⋮ On reverse and general definite tree languages ⋮ Stone duality, topological algebra, and recognition. ⋮ A Kleene Theorem for Forest Languages ⋮ Unnamed Item ⋮ From Tree Automata to Rational Tree Expressions ⋮ Logic and rational languages of scattered and countable series-parallel posets ⋮ TREE AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED LOGIC: REDUCTION ALGORITHM AND DECISION PROBLEMS ⋮ Weighted Automata and Logics on Infinite Graphs ⋮ On Finite and Polynomial Ambiguity of Weighted Tree Automata ⋮ Forward analysis for WSTS, part I: completions ⋮ Pomset Languages of Finite Step Transition Systems ⋮ Compact Representation for Answer Sets of n-ary Regular Queries ⋮ Generalized sequential machine maps ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ Construction of tree automata from regular expressions ⋮ Probabilistic tree automata and context free languages ⋮ Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics ⋮ Decidable call by need computations in term rewriting (extended abstract) ⋮ Reasoning about XML constraints based on XML-to-relational mappings ⋮ Combining Theories with Shared Set Operations ⋮ Regular-like tree expressions ⋮ Decidable first-order transition logics for PA-processes ⋮ Relating word and tree automata ⋮ Projection for Büchi Tree Automata with Constraints between Siblings ⋮ Cascade Products and Temporal Logics on Finite Trees ⋮ Bottom-Up derivatives of tree expressions ⋮ Characterizing weighted MSO for trees by branching transitive closure logics ⋮ A link between multioperator and tree valuation automata and logics ⋮ Locally finite properties of data structures and their computation ⋮ Modulo-counting quantifiers over finite trees ⋮ Alternating tree automata ⋮ The greatest fixed-points and rational omega-tree languages ⋮ Reductions in tree replacement systems ⋮ A branching time logic with past operators ⋮ The translation power of top-down tree-to-graph transducers ⋮ A logical approach to locality in pictures languages ⋮ Automata-theoretic techniques for modal logics of programs ⋮ Topological characterizations of infinite tree languages ⋮ Axiomatizing the equational theory of regular tree languages ⋮ Definable transductions and weighted logics for texts ⋮ Decidability of the minimization of fuzzy tree automata with membership values in complete lattices ⋮ Dominance constraints in stratified context unification ⋮ Monadic second-order definable text languages ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Weighted tree automata and weighted logics ⋮ Logic programming approach to automata-based decision procedures ⋮ Weighted tree automata with constraints ⋮ On the relationship of congruence closure and unification ⋮ Automata for XML -- a survey ⋮ Logical description of context-free graph languages ⋮ On the minimization of XML schemas and tree automata for unranked trees ⋮ Tree algebras and varieties of tree languages ⋮ Cellular automata between sofic tree shifts ⋮ Tree transducers, L systems, and two-way machines ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Machines in a category ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Büchi context-free languages ⋮ Research in the theory of inductive inference by GDR mathematicians - A survey ⋮ Coding tree languages based on lattice-valued logic ⋮ Conjunctive query containment over trees using schema information ⋮ Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic ⋮ The congruence theory of closure properties of regular tree languages ⋮ Recognizable formal power series on trees ⋮ Compact representation for answer sets of \(n\)-ary regular queries ⋮ Discrete-time control for rectangular hybrid automata ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ Static analysis of XML security views and query rewriting ⋮ On rational definitions in complete algebras without rank ⋮ Systolic trees and systolic language recognition by tree automata ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ A regular characterization of graph languages definable in monadic second-order logic ⋮ Generalized automata on infinite trees and Muller-McNaughton's theorem ⋮ Multidimensional trees ⋮ 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 ⋮ Alphabetic tree relations ⋮ Automata for unordered trees ⋮ Weighted automata and logics for infinite nested words ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ Another variation on the common subexpression problem ⋮ On characterization of fuzzy tree pushdown automata ⋮ Linear delay enumeration and monadic second-order logic ⋮ Monadic second-order model-checking on decomposable matroids ⋮ A note on partially ordered tree automata ⋮ Decidable containment of recursive queries ⋮ 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 ⋮ Surface tree languages and parallel derivation trees ⋮ Basic tree transducers ⋮ Automata on infinite objects and their applications to logic and programming ⋮ A generalized approach to formal languages ⋮ A Kleene theorem for weighted tree automata over tree valuation monoids ⋮ Bottom-up unranked tree-to-graph transducers for translation into semantic graphs ⋮ Iterating iterated substitution ⋮ IO and OI. I ⋮ IO and OI. II ⋮ Determinacy and rewriting of functional top-down and MSO tree transformations ⋮ Pumping lemmas for term languages ⋮ Characterizations of recognizable weighted tree languages by logic and bimorphisms ⋮ A unifying survey on weighted logics and weighted automata. Core weighted logic: minimal and versatile specification of quantitative properties ⋮ An axiom system for the weak monadic second order theory of two successors ⋮ Fixed-point constructions in order-enriched categories ⋮ Kleene and Büchi theorems for weighted forest languages over M-monoids ⋮ Linear weighted tree automata with storage and inverse linear tree homomorphisms ⋮ Bounds in the propagation of selection into logic programs ⋮ The equivalence of bottom-up and top-down tree-to-graph transducers ⋮ Principal abstract families of weighted tree languages ⋮ Logic for \(\omega\)-pushdown automata ⋮ Nondeterministic operations on finite relational structures ⋮ Series-parallel languages and the bounded-width property ⋮ Automata on finite trees ⋮ Algebra for trees ⋮ Lattice-valued tree pushdown automata: pumping lemma and closure properties ⋮ Recursive information transducers: Computation models ⋮ 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 ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Tree pushdown automata ⋮ Uniform and nonuniform recognizability. ⋮ Sequentiality, monadic second-order logic and tree automata. ⋮ Ordering constraints over feature trees expressed in second-order monadic logic. ⋮ Rationality in algebras with a series operation ⋮ Query automata over finite trees ⋮ Macro tree transducers ⋮ An operational and denotational approach to non-context-freeness ⋮ wMSO theories as grammar formalisms

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:5538923&oldid=30134043"