文章基本信息

标题：Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic
本地全文：下载
作者：Dietrich Kuske
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：1
页码：467-478
DOI：10.4230/LIPIcs.STACS.2008.1366
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Logic in computer science; Rabin's tree theorem