The monadic second order theory of all countable ordinals

DOI10.1007/BFB0082720zbMath0298.02050OpenAlexW4206459686MaRDI QIDQ1214411

Dirk Siefkes, J. Richard Buchi

Publication date: 1973

Published in: Lecture Notes in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0082720

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items (33)

On omega context free languages which are Borel sets of infinite rank. ⋮ Closure properties of locally finite \(\omega\)-languages ⋮ The complementation problem for Büchi automata with applications to temporal logic ⋮ On decidability properties of local sentences ⋮ Complementing deterministic Büchi automata in polynomial time ⋮ Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations ⋮ Ambiguity in omega context free languages ⋮ Borel hierarchy and omega context free languages. ⋮ Büchi context-free languages ⋮ Temporal logics over linear time domains are in PSPACE ⋮ On algebraic array theories ⋮ Selection over classes of ordinals expanded by monadic predicates ⋮ On the structure of random unlabelled acyclic graphs. ⋮ Constructivizations of Boolean algebras ⋮ Inferring answers to queries ⋮ A hierarchy of tree-automatic structures ⋮ Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems ⋮ The recursive sets in certain monadic second order fragments of arithmetic ⋮ Expressing cardinality quantifiers in monadic second-order logic over chains ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES ⋮ Locally finite languages ⋮ Topological properties of omega context-free languages ⋮ Wadge hierarchy of omega context-free languages ⋮ The full binary tree cannot be interpreted in a chain ⋮ Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes ⋮ An axiom system for the weak monadic second order theory of two successors ⋮ On the complementation of Büchi automata ⋮ On Müller context-free grammars ⋮ Test sets for equality of terms in the additive structure of ordinals augmented with right multiplication by \(\omega\) ⋮ REASONING ABOUT TRANSFINITE SEQUENCES ⋮ Hierarchies of weak automata and weak monadic formulas ⋮ The structure of the models of decidable monadic theories of graphs

This page was built for publication: The monadic second order theory of all countable ordinals