Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Kuske, Dietrich https://www.dagstuhl.de/lipics License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-13668
URL:

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

pdf-format:


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:LIPIcs:2008:1366,
  author =	{Dietrich Kuske},
  title =	{{Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{467--478},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1366},
  URN =		{urn:nbn:de:0030-drops-13668},
  doi =		{10.4230/LIPIcs.STACS.2008.1366},
  annote =	{Keywords: Logic in computer science, Rabin's tree theorem}
}

Keywords: Logic in computer science, Rabin's tree theorem
Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue date: 2008
Date of publication: 06.02.2008


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI