Search

• < Previous
• 1
• 2
• Next >

---

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

---

Definable decompositions for graphs of bounded linear cliquewidth

Mikołaj Bojańczyk ; Martin Grohe ; Michał Pilipczuk.

We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of&nbsp;[&hellip;]

---

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

---

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

---

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

---

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

---

An extension of data automata that captures XPath

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

We define a new kind of automata recognizing properties of data words or data trees and prove that the automata capture all queries definable in Regular XPath. We show that the automata-theoretic approach may be applied to answer decidability and expressibility questions for XPath.

---

Tree Languages Defined in First-Order Logic with One Quantifier Alternation

Mikolaj Bojanczyk ; Luc Segoufin.

We study tree languages that can be defined in \Delta_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a first-order formula whose quantifier prefix is . For the quantifier free part we consider two signatures, either the&nbsp;[&hellip;]

---

Two-Way Unary Temporal Logic over Trees

Mikolaj Bojanczyk.

We consider a temporal logic EF+F^-1 for unranked, unordered finite trees. The logic has two operators: EF\phi, which says "in some proper descendant \phi holds", and F^-1\phi, which says "in some proper ancestor \phi holds". We present an algorithm for deciding if a regular language of unranked&nbsp;[&hellip;]

---

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

---