1 Search Results for "Moskvina, Anastasia"


Document
Infinite and Bi-infinite Words with Decidable Monadic Theories

Authors: Dietrich Kuske, Jiamou Liu, and Anastasia Moskvina

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)


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.

Cite as

Dietrich Kuske, Jiamou Liu, and Anastasia Moskvina. Infinite and Bi-infinite Words with Decidable Monadic Theories. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 472-486, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{kuske_et_al:LIPIcs.CSL.2015.472,
  author =	{Kuske, Dietrich and Liu, Jiamou and Moskvina, Anastasia},
  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 =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.472},
  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}
}
  • Refine by Author
  • 1 Kuske, Dietrich
  • 1 Liu, Jiamou
  • 1 Moskvina, Anastasia

  • Refine by Classification

  • Refine by Keyword
  • 1 bi-infinite words
  • 1 infinite words
  • 1 monadic second order logic

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail