Search

• < Previous
• 1
• 2
• Next >

---

Boundedness in languages of infinite words

Mikołaj Bojańczyk ; Thomas Colcombet.

We define a new class of languages of $\omega$-words, strictly extending $\omega$-regular languages. One way to present this new class is by a type of regular expressions. The new expressions are an extension of $\omega$-regular expressions where two new variants of the Kleene star $L^*$ are&nbsp;[&hellip;]

---

Undecidability of a weak version of MSO+U

Mikołaj Bojańczyk ; Laure Daviaud ; Bruno Guillon ; Vincent Penelle ; A. V. Sreejith.

We prove the undecidability of MSO on $\omega$-words extended with the second-order predicate $U_1(X)$ which says that the distance between consecutive positions in a set $X \subseteq \mathbb{N}$ is unbounded. This is achieved by showing that adding $U_1$ to MSO gives a logic with the same&nbsp;[&hellip;]

---