Search

• < Previous
• 1
• Next >

---

Infinite and Bi-infinite Words with Decidable Monadic Theories

Dietrich Kuske ; Jiamou Liu ; Anastasia Moskvina.

We study word structures of the form $(D,<,P)$ where $D$ is either $\mathbb{N}$ or $\mathbb{Z}$, $<$ is the natural linear ordering on $D$ and $P\subseteq D$ is a predicate on $D$. In particular we show: (a) The set of recursive $\omega$-words with decidable monadic second order theories is&nbsp;[&hellip;]

---

Tree-Automatic Well-Founded Trees

Martin Huschenbett ; Alexander Kartzow ; Jiamou Liu ; Markus Lohrey.

We investigate tree-automatic well-founded trees. Using Delhomme's decomposition technique for tree-automatic structures, we show that the (ordinal) rank of a tree-automatic well-founded tree is strictly below omega^omega. Moreover, we make a step towards proving that the ranks of tree-automatic&nbsp;[&hellip;]

---