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

---

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

---

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

---