2026-07-22T04:53:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1407 2024-03-06T11:07:45Z ddc:004 open_access

Compatibility of Shelah and Stupp's and of Muchnik's iteration with fragments of monadic second order logic Kuske, Dietrich Logic in computer science Rabin's tree theorem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dietrich Kuske 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07441.4 urn:nbn:de:0030-drops-14078 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.4 eng https://creativecommons.org/licenses/by/4.0/legalcode