47 citations · 159 across the 27 of their papers we have counts for
33 papers
Trees in graphs of large linear cliquewidth
Mikołaj Bojańczyk, Pierre Ohlmann
The Pathwidth Theorem states that if a class of graphs has unbounded pathwidth, then it contains all trees as graph minors. We prove a similar result for dense graphs. More precise…
Separator logic and star-free expressions for graphs
Mikolaj Bojanczyk
We describe two formalisms for defining graph languages, and prove that they are equivalent: 1. Separator logic. This is first-order logic on graphs which is allowed to use the edg…
Single use register automata for data words
Mikołaj Bojańczyk, Rafał Stefański
Our starting point are register automata for data words, in the style of Kaminski and Francez. We study the effects of the single-use restriction, which says that a register is emp…
String-to-String Interpretations with Polynomial-Size Output
Mikołaj Bojańczyk, Sandra Kiefer, Nathan Lhote
String-to-string MSO interpretations are like Courcelle's MSO transductions, except that a single output position can be represented using a tuple of input positions instead of jus…
MSO+nabla is undecidable
Mikołaj Bojańczyk, Edon Kelmendi, Michał Skrzypczak
This paper is about an extension of monadic second-order logic over the full binary tree, which has a quantifier saying ``almost surely a branch π \in {0, 1}^w satisfies a formula…
Polyregular Functions
Mikołaj Bojańczyk
This paper is about certain string-to-string functions, called the polyregular functions. These are like the regular string-to-string functions, except that they can have polynomia…
Regular tree languages in low levels of the Wadge Hierarchy
Mikołaj Bojańczyk, Filippo Cavallari, Thomas Place +1
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 decidabi…
Two monads for graphs
Mikolaj Bojanczyk
An introduction to algebras for graphs, based on Courcelle's algebras of hyperedge replacement and vertex replacement. The paper uses monad notation.
Regular and First Order List Functions
Mikolaj Bojanczyk, Laure Daviaud, Krishna Shankara Narayanan
We define two classes of functions, called regular (respectively, first-order) list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pair…
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 de…
Star Height via Games
Mikolaj Bojanczyk
This paper proposes a new algorithm deciding the star height problem. As shown by Kirsten, the star height problem reduces to a problem concerning automata with counters, called li…
Boundedness in languages of infinite words
Mikołaj Bojańczyk, Thomas Colcombet
We define a new class of languages of -words, strictly extending -regular languages. One way to present this new class is by a type of regular expressions. The new expression…
Emptiness of zero automata is decidable
Mikolaj Bojańczyk, Hugo Gimbert, Edon Kelmendi
Zero automata are a probabilistic extension of parity automata on infinite trees. The satisfiability of a certain probabilistic variant of mso, called tmso + zero, reduces to the e…
It is undecidable if two regular tree languages can be separated by a deterministic tree-walking automaton
Mikołaj Bojańczyk
The following problem is shown undecidable: given regular languages L,K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L…
Some connections between universal algebra and logics for trees
Mikołaj Bojańczyk, Henryk Michalewski
One of the major open problems in automata and logic is the following: is there an algorithm which inputs a regular tree language and decides if the language can be defined in firs…
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…
On the Regular Emptiness Problem of Subzero Automata
Henryk Michalewski, Matteo Mio, Mikołaj Bojańczyk
Subzero automata is a class of tree automata whose acceptance condition can express probabilistic constraints. Our main result is that the problem of determining if a subzero autom…
Definability equals recognizability for graphs of bounded treewidth
Mikołaj Bojańczyk, Michał Pilipczuk
We prove a conjecture of Courcelle, which states that a graph property is definable in MSO with modular counting predicates on graphs of constant treewidth if, and only if it is re…
Recognisable languages over monads
Mikołaj Bojańczyk
The principle behind algebraic language theory for various kinds of structures, such as words or trees, is to use a compositional function from the structures into a finite set. To…
The MSO+U theory of (N, <) is undecidable
Mikołaj Bojańczyk, Paweł Parys, Szymon Toruńczyk
We consider the logic MSO+U, which is monadic second-order logic extended with the unbounding quantifier. The unbounding quantifier is used to say that a property of finite sets ho…
Decomposition Theorems and Model-Checking for the Modal -Calculus
Mikolaj Bojanczyk, Christoph Dittmann, Stephan Kreutzer
We prove a general decomposition theorem for the modal -calculus in the spirit of Feferman and Vaught's theorem for disjoint unions. In particular, we show that if a struc…
Weak MSO+U with Path Quantifiers over Infinite Trees
Mikołaj Bojańczyk
This paper shows that over infinite trees, satisfiability is decidable for weak monadic second-order logic extended by the unbounding quantifier U and quantification over infinite…
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 ensui…
Transducers with origin information
Mikołaj Bojańczyk
Call a string-to-string transducer regular if it can be realised by one of the following equivalent models: mso transductions, two-way deterministic automata with output, and strea…