Definability in the monadic second-order theory of successor

DOI10.2307/2271090zbMath0209.02203OpenAlexW4231685078MaRDI QIDQ5609381

J. Richard Buchi, Lawrence H. Landweber

Publication date: 1969

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1095&context=cstech

Mathematics Subject Classification ID

Second- and higher-order arithmetic and fragments (03F35) Hierarchies of computability and definability (03D55)

Related Items

Infinite-word languages and continuous mappings, On the classification of computable languages, Decision problems forω-automata, Computation as social agency: what, how and who, On the classification of recursive languages, Model-checking iterated games, Enumerating grammar-based extractions, Distributed synthesis is simply undecidable, The recursive sets in certain monadic second order fragments of arithmetic, Doomsday equilibria for omega-regular games, The Borel hierarchy is infinite in the class of regular sets of trees, On Monadic Theories of Monadic Predicates, A list of arithmetical structures complete with respect to the first-order definability, From automatic structures to automatic groups., Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages, The theory of successor with an extra predicate, On the bounded monadic theory of well-ordered structures, Tighter Bounds for the Determinisation of Büchi Automata, Unnamed Item, Logic, semigroups and automata on words, Finite-state \(\omega\)-languages, The monadic theory of morphic infinite words and generalizations, Decidability and undecidability of theories with a predicate for the primes

Cites Work

• Hierarchies of number-theoretic predicates
• Testing and generating infinite sequences by a finite automaton
• Unnamed Item