License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07441.4
URN: urn:nbn:de:0030-drops-14078
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1407/
|
Go to the corresponding Portal |
Kuske, Dietrich
Compatibility of Shelah and Stupp's and of Muchnik's iteration with fragments of monadic second order logic
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.
BibTeX - Entry
@InProceedings{kuske:DagSemProc.07441.4,
author = {Kuske, Dietrich},
title = {{Compatibility of Shelah and Stupp's and of Muchnik's iteration with fragments of monadic second order logic}},
booktitle = {Algorithmic-Logical Theory of Infinite Structures},
pages = {1--14},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2008},
volume = {7441},
editor = {Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2008/1407},
URN = {urn:nbn:de:0030-drops-14078},
doi = {10.4230/DagSemProc.07441.4},
annote = {Keywords: Logic in computer science, Rabin's tree theorem}
}
|
Keywords: |
|
Logic in computer science, Rabin's tree theorem |
|
Collection: |
|
07441 - Algorithmic-Logical Theory of Infinite Structures |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
09.04.2008 |
