Search

• < Previous
• 1
• Next >

---

Automata theory in nominal sets

Mikołaj Bojańczyk ; Bartek Klin ; Sławomir Lasota.

We study languages over infinite alphabets equipped with some structure that can be tested by recognizing automata. We develop a framework for studying such alphabets and the ensuing automata theory, where the key role is played by an automorphism group of the alphabet. In the process, we generalize&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;]

---