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 ⋮ 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 ⋮ Stone duality, topological algebra, and recognition. ⋮ Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure ⋮ Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure ⋮ Decidable Expansions of Labelled Linear Orderings ⋮ An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning ⋮ 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 ⋮ Recursive unary algebras and trees ⋮ The finite graph problem for two-way alternating automata. ⋮ Future temporal logic needs infinitely many modalities ⋮ The monadic second order logic of graphs. VI: On several representations of graphs by relational structures ⋮ A branching time logic with past operators ⋮ Progress measures, immediate determinacy, and a subset construction for tree automata ⋮ Memoryless determinacy of parity and mean payoff games: a simple proof ⋮ Rabin tree automata and finite monoids ⋮ Graded modalities in strategy logic ⋮ Chain automata ⋮ Somewhat finite approaches to infinite sentences. ⋮ The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs ⋮ Determinization and memoryless winning strategies ⋮ On control of systems modelled as deterministic Rabin automata ⋮ Order-couniversality of the complete infinitary tree: an application of zero-divisor graphs ⋮ A first-order axiomatization of the theory of finite trees ⋮ The Lindenbaum-Tarski algebra for Boolean algebras with distinguished ideals ⋮ Propositional quantification in the topological semantics for \(\mathbf S4\) ⋮ Finite-state strategies in delay games ⋮ Fixed point characterization of infinite behavior of finite-state systems ⋮ A first order logic of effects ⋮ Program schemata vs. automata for decidability of program logics ⋮ Finite automata on timed \(\omega\)-trees ⋮ Infinite-duration poorman-bidding games ⋮ The complexity of the temporal logic with ``until over general linear time ⋮ From bidirectionality to alternation.
This page was built for publication: Decidability of Second-Order Theories and Automata on Infinite Trees
