License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-14078
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1407/
Kuske, Dietrich

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

pdf-format:
Dokument 1.pdf (258 KB)

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:DSP:2008:1407,
  author =	{Dietrich Kuske},
  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},
  year =	{2008},
  editor =	{Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
  number =	{07441},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1407},
  annote =	{Keywords: Logic in computer science, Rabin's tree theorem}
}

Keywords: Logic in computer science, Rabin's tree theorem
Seminar: 07441 - Algorithmic-Logical Theory of Infinite Structures
Issue date: 2008
Date of publication: 09.04.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI