Infinite and bi-infinite words with decidable monadic theories

Kuske, Dietrich GND; Liu, Jiamou; Moskvina, Anastasia

We study word structures of the form (D, <, P) where D is either N or Z, < is the natural linear ordering on D and P [subset of or equal to] D is a predicate on D. In particular we show: (a) The set of recursive [omega]-words with decidable monadic second order theories is [n-ary summation]3-complete. (b) Known characterisations of the [omega]-words with decidable monadic second order theories are transfered to the corresponding question for bi-infinite words. (c) We show that such "tame" predicates P exist in every Turing degree. (d) We determine, for P [subset of or equal to] Z, the number of predicates Q [subset of or equal to] Z such that (Z, ≤, P) and (Z, ≤, Q) are indistinguishable by monadic second order formulas. Through these results we demonstrate similarities and differences between logical properties of infinite and bi-infinite words.

Cite

Citation style:

Kuske, Dietrich / Liu, Jiamou / Moskvina, Anastasia: Infinite and bi-infinite words with decidable monadic theories. 2018.

Access Statistic

Total:
Downloads:
Abtractviews:
Last 12 Month:
Downloads:
Abtractviews:

open graphic

Rights

Use and reproduction:

Export