文章基本信息

标题：Infinite and Bi-infinite Words with Decidable Monadic Theories
本地全文：下载
作者：Dietrich Kuske ; Jiamou Liu ; Anastasia Moskvina 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：41
页码：472-486
DOI：10.4230/LIPIcs.CSL.2015.472
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study word structures of the form (D,<=,P) where D is either N or Z, <= is a linear ordering on D and P in D is a predicate on D. In particular we show: (a) The set of recursive omega-words with decidable monadic second order theories is Sigma_3-complete. (b) We characterise those sets P subset of Z that yield bi-infinite words (Z,<=,P) with decidable monadic second order theories. (c) We show that such "tame" predicates P exist in every Turing degree. (d) We determine, for P subset of Z, the number of predicates Q subset of Z such that (Z,<=,P) and (Z,<=,Q) are indistinguishable. Through these results we demonstrate similarities and differences between logical properties of infinite and bi-infinite words.
关键词：infinite words; bi-infinite words; monadic second order logic