2 citations · 3 across the 5 of their papers we have counts for
5 papers
Rank-decreasing transductions
Mikołaj Bojańczyk, Pierre Ohlmann
We propose to study transformations on graphs, and more generally structures, by looking at how the cut-rank (as introduced by Oum) of subsets is affected when going from the input…
Polyregular functions on unordered trees of bounded height
Mikołaj Bojańczyk, Bartek Klin
We consider injective first-order interpretations that input and output trees of bounded height. The corresponding functions have polynomial output size, since a first-order interp…
The category of MSO transductions
Mikołaj Bojańczyk
MSO transductions are binary relations between structures which are defined using monadic second-order logic. MSO transductions form a category, since they are closed under composi…
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…
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…