License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2015.472
URN: urn:nbn:de:0030-drops-54325
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5432/
Go to the corresponding LIPIcs Volume Portal

Kuske, Dietrich ; Liu, Jiamou ; Moskvina, Anastasia

Infinite and Bi-infinite Words with Decidable Monadic Theories

pdf-format:
29.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{kuske_et_al:LIPIcs:2015:5432,
  author =	{Dietrich Kuske and Jiamou Liu and Anastasia Moskvina},
  title =	{{Infinite and Bi-infinite Words with Decidable Monadic Theories}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{472--486},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Stephan Kreutzer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5432},
  URN =		{urn:nbn:de:0030-drops-54325},
  doi =		{10.4230/LIPIcs.CSL.2015.472},
  annote =	{Keywords: infinite words, bi-infinite words, monadic second order logic}
}

Keywords: infinite words, bi-infinite words, monadic second order logic
Collection: 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Issue Date: 2015
Date of publication: 07.09.2015

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