Search

• < Previous
• 1
• Next >

---

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;]

---

A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra

Mikołaj Bojańczyk ; Bartek Klin.

$\omega$-clones are multi-sorted structures that naturally emerge as algebras for infinite trees, just as $\omega$-semigroups are convenient algebras for infinite words. In the algebraic theory of languages, one hopes that a language is regular if and only if it is recognized by an algebra that is&nbsp;[&hellip;]

---

Regular tree languages in low levels of the Wadge Hierarchy

Mikołaj Bojańczyk ; Filippo Cavallari ; Thomas Place ; Michał Skrzypczak.

In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidability for each of the finite levels of the hierarchy; for the class of the Boolean combinations of open sets&nbsp;[&hellip;]

---

Optimizing tree decompositions in MSO

Mikołaj Bojańczyk ; Michał Pilipczuk.

The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly suboptimal) width k, compute an optimum-width tree decomposition of the graph. In this work, we prove that this problem&nbsp;[&hellip;]

---