Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic

2008/01/01 by Dietrich Kuske, Kuske, Dietrich
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #Logic in computer science #Logic, Reasoning, and Knowledge #Rabin's tree theorem

paper · doi:10.4230/dagsemproc.07441.4

openalex publication_date 2008/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the relation between the theory of the iterations in the sense of Shelah-Stupp and of Muchnik, resp., and the theory of the base structure for several logics. These logics are obtained from the restriction of set quantification in monadic second order logic to certain subsets like, e.g., finite sets, chains, and finite unions of chains. We show that these theories of the Shelah-Stupp iteration can be reduced to corresponding theories of the base structure. This fails for Muchnik's iteration.

Related

• On Expansions of Monadic Second-Order Logic with Dynamical Predicates
• Interpreting the monadic second order theory of one successor in expansions of the real line
• The MSO+U theory of (N, <) is undecidable
• Lattices of Logical Fragments over Words
• Kripke trick and decidability of monadic fragments of modal and superintuitionistic logics