10.4230/LIPICS.STACS.2008.1366
Kuske, Dietrich
Dietrich
Kuske
Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Logic in computer science
Rabin's tree theorem
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13668
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
41
467
478
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
186966 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 467-478