Document Open Access Logo

Infinite and Bi-infinite Words with Decidable Monadic Theories

Authors Dietrich Kuske, Jiamou Liu, Anastasia Moskvina

PDF
Thumbnail PDF

File

LIPIcs.CSL.2015.472.pdf
  • Filesize: 468 kB
  • 15 pages

Document Identifiers

Author Details

Dietrich Kuske
Jiamou Liu
Anastasia Moskvina

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.CSL.2015.472

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.

Subject Classification

Keywords
  • infinite words
  • bi-infinite words
  • monadic second order logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alexis Bés and Alexander Rabinovich. Decidable expansions of labelled linear orderings. Logical Methods in Computer Science, 7(2), 2011. Google Scholar
  2. J. Richard Büchi. On a decision method in restricted second order arithmetic. In Proceedings of the Interantional Congress on Methodology and Philosophy of Science, pages 1-11. Stanford University Press, 1962. Google Scholar
  3. J. Richard Büchi and Lawrence Landweber. Definability in the monadic second-order theory of successor. Journal of Symbolic Logic, 34:166-170, 1969. Google Scholar
  4. Olivier Carton and Wolfgang Thomas. The monadic theory of morphic infinite words and generalizations. Information and Computation, 176(1):51-56, 2002. Google Scholar
  5. Calvin Elgot and Michael O. Rabin. Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. J. of Symbolic Logic, 31(2):169-181, 1996. Google Scholar
  6. Dominique Perrin and Jean-Éric Pin. Infinite words: automata, semigroups, logic and games, volume 141 of Pure and Applied Mathematics Series. Elsevier, 2004. Google Scholar
  7. Dominique Perrin and Paul Schupp. Automata on the integers, recurrence distinguishability, and the equivalence and decidability of monadic theories. In Proceedings of the Symposium on Logic in Computer Science, pages 301-304. IEEE Computer Society Press, 1986. Google Scholar
  8. Alexander Rabinovich. On decidability of monadic logic of order over the naturals extended by monadic predicates. Information and Computation, 205(6):870-889, 2007. Google Scholar
  9. Alexander Rabinovich and Wolfgang Thomas. Decidable theories of the ordering of natural numbers with unary predicates. In Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings, Lecture Notes in Computer Science, pages 562-574. Springer, 2006. Google Scholar
  10. Alexei Semenov. Decidability of monadic theories. In Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia, September 3-7, 1984, Proceedings, Lecture Notes in Computer Science, pages 162-175. Springer, 1984. Google Scholar
  11. Alexei Semenov. Logical theories of one-place functions on the set of natural numbers. Mathematics of the USSR - Izvestia, 22:587-618, 1984. Google Scholar
  12. Saharon Shelah. The monadic theory of order. Annals of Mathematics, 102:379-419, 1957. Google Scholar
  13. Dirk Siefkes. Decidable extensions of monadic second order successor arithmetic. Automatentheorie und formale Sprachen, pages 441-472, 1969. Google Scholar
  14. Robert Soare. Recursively enumerable sets and degrees: A Study of Computable Functions and Computably Generated Sets. Perspectives in Mathematical Logic. Springer, 1987. Google Scholar
  15. Wolfgang Thomas. Languages, automata, and logic. In Handbook of Formal Languages, volume 3, pages 389-455. Springer, 1997. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact