Decidability of Second-Order Theories and Automata on Infinite Trees
From MaRDI portal
Publication:5625141
DOI10.2307/1995086zbMath0221.02031OpenAlexW4240244556WikidataQ30052266 ScholiaQ30052266MaRDI QIDQ5625141
Publication date: 1969
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://projecteuclid.org/euclid.bams/1183529958
Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)
Related Items (only showing first 100 items - show all)
Index Problems for Game Automata ⋮ On Composing Finite Forests with Modal Logics ⋮ Solving Infinite Games in the Baire Space ⋮ Measure Quantifier in Monadic Second Order Logic ⋮ A propositional dense time logic ⋮ Conditional rewrite rule systems with built-in arithmetic and induction ⋮ Multi-Valued Reasoning about Reactive Systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deciding equivalence of finite tree automata ⋮ Automatic presentations of structures ⋮ Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words ⋮ On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic ⋮ Reachability games and parity games ⋮ Reasoning about Quality and Fuzziness of Strategic Behaviors ⋮ Model completion of scaled lattices and co‐Heyting algebras of p‐adic semi‐algebraic sets ⋮ The lattice of definability: origins, recent developments, and further directions ⋮ On the Boolean Closure of Deterministic Top-Down Tree Automata ⋮ An interval temporal logic characterization of extended \(\omega\)-regular languages ⋮ Generalized quantifiers and well orderings ⋮ Unnamed Item ⋮ Liminf progress measures ⋮ Compatibility of refining and controlling plant automata with bisimulation quotients ⋮ First-order separation over countable ordinals ⋮ Modal logics and local quantifiers: a zoo in the elementary hierarchy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Abstract cyclic proofs ⋮ A hierarchy of tree-automatic structures ⋮ Complete theories of unars ⋮ Deciding low levels of tree-automata hierarchy ⋮ Pebble Weighted Automata and Weighted Logics ⋮ Monadic Second Order Logic And Its Fragments ⋮ On Expressive Power of Regular Expressions over Infinite Orders ⋮ Further Generalizations of Results on Structures of Continuous Functions ⋮ Grid structures and undecidable constraint theories ⋮ A list of arithmetical structures complete with respect to the first-order definability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Using partial orders for the efficient verification of deadlock freedom and safety properties ⋮ Free \(\mu\)-lattices ⋮ Automata on infinite trees with counting constraints ⋮ Computing the Rabin Index of a Parity Automaton ⋮ Unnamed Item ⋮ Tree Automata over Infinite Alphabets ⋮ Selection and Uniformization Problems in the Monadic Theory of Ordinals: A Survey ⋮ Church’s Problem and a Tour through Automata Theory ⋮ Incremental reasoning on monadic second-order logics with logic programming ⋮ Synthesis of compact strategies for coordination programs ⋮ A direct symbolic algorithm for solving stochastic Rabin games ⋮ Axiomatizability of propositionally quantified modal logics on relational frames ⋮ Stone duality, topological algebra, and recognition. ⋮ A proof system for finite trees ⋮ Some extensions to propositional mean-value calculus: expressiveness and decidability ⋮ Automated temporal reasoning about reactive systems ⋮ An automata-theoretic approach to linear temporal logic ⋮ Controller synthesis against omega-regular specifications: a funnel-based control approach ⋮ A weak theory of building blocks ⋮ Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure ⋮ Theoretical computer science: computability, decidability and logic ⋮ Theoretical computer science: computational complexity ⋮ Monadic monadic second order logic ⋮ Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure ⋮ Fair \(\omega \)-regular games ⋮ Decidable Expansions of Labelled Linear Orderings ⋮ On the 1-decidability of Boolean algebras with one distinguished ideal ⋮ An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning ⋮ Non-emptiness test for automata over words indexed by the reals and rationals ⋮ Logic and rational languages of scattered and countable series-parallel posets ⋮ An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning ⋮ Monoidal-closed categories of tree automata ⋮ On Repetition Languages ⋮ A Survey of Bidding Games on Graphs (Invited Paper) ⋮ Unnamed Item ⋮ COMPLETE ADDITIVITY AND MODAL INCOMPLETENESS ⋮ A Characterisation of Pi^0_2 Regular Tree Languages ⋮ Unambiguity in Automata Theory ⋮ A Tentative Approach for the Wadge-Wagner Hierarchy of Regular Tree Languages of Index [0, 2] ⋮ An upper bound on the complexity of recognizable tree languages ⋮ Towards Efficient Verification of Systems with Dynamic Process Creation ⋮ Unnamed Item ⋮ Projection for Büchi Tree Automata with Constraints between Siblings ⋮ Rabin vs. Streett Automata ⋮ Backward Deterministic Büchi Automata on Infinite Words ⋮ Tree-automatic scattered linear orders ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ Satisfiability of \(\operatorname{ECTL}^\ast\) with constraints ⋮ Variétés d'automates descendants d'arbres infinis ⋮ Construction of decidable singular theories of two successor functions with an extra predicate ⋮ Infinite-word languages and continuous mappings ⋮ The greatest fixed-points and rational omega-tree languages ⋮ Elementary and algebraic properties of the Arens-Kaplansky constructions ⋮ The theory of ends, pushdown automata, and second-order logic ⋮ Recursive categoricity and recursive stability
This page was built for publication: Decidability of Second-Order Theories and Automata on Infinite Trees
