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

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 (only showing first 100 items - show all)

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 ⋮ Reasoning About Data Trees Using CHCs ⋮ 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. ⋮ Regular planar monoidal languages ⋮ Linear-time logics -- a coalgebraic perspective ⋮ A Kleene Theorem for Forest Languages ⋮ Unnamed Item ⋮ Theoretical computer science: computational complexity ⋮ Top-down complementation of automata on finite trees ⋮ Twin-treewidth: a single-exponential logic-based approach ⋮ Monadic monadic second order logic ⋮ From Tree Automata to Rational Tree Expressions ⋮ Rational weighted tree languages with storage ⋮ The weighted HOM-problem over fields ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Realization of Events by Logical Nets
• The first order properties of products of algebraic systems
• Weak Second‐Order Arithmetic and Finite Automata
• Classes of Predictably Computable Functions
• Restricted Set-Theoretical Definitions in Arithmetic
• Beitrag zur Aerodynamik eines schwingenden Gitters II (Unterschallströmung)

This page was built for publication: Generalized finite automata theory with an application to a decision problem of second-order logic