3 citations · 10 across the 8 of their papers we have counts for
9 papers
The Finite Length Property of the Rado Graph and Friends
Jingjie Yang, Mikołaj Bojańczyk, Bartek Klin
An infinite structure has the finite length property (over a given field) if, for each of its finite powers, chains of equivariant subspaces in the corresponding free vector space…
Folding interpretations
Mikołaj Bojańczyk
We study the polyregular string-to-string functions, which are certain functions of polynomial output size that can be described using automata and logic. We describe a system of c…
On the growth rate of polyregular functions
Mikołaj Bojańczyk
We consider polyregular functions, which are certain string-to-string functions that have polynomial output size. We prove that a polyregular function has output size $\mathcal O(n…
Monadic Monadic Second Order Logic
Mikołaj Bojańczyk, Bartek Klin, Julian Salamanca
One of the main reasons for the correspondence of regular languages and monadic second-order logic is that the class of regular languages is closed under images of surjective lette…
Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata
Mikołaj Bojańczyk, Joanna Fijalkow, Bartek Klin +1
We develop a theory of vector spaces spanned by orbit-finite sets. Using this theory, we give a decision procedure for equivalence of weighted register automata, which are the comm…
Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic
Mikołaj Bojańczyk
These are lecture notes on the algebraic approach to regular languages. The classical algebraic approach is for finite words; it uses semigroups instead of automata. However, the a…
Extensions of -Regular Languages
Mikołaj Bojańczyk, Edon Kelmendi, Rafał Stefański +1
We consider extensions of monadic second order logic over -words, which are obtained by adding one language that is not -regular. We show that if the added language has a…
First-order tree-to-tree functions
Mikołaj Bojańczyk, Amina Doumane
We study tree-to-tree transformations that can be defined in first-order logic or monadic second-order logic. We prove a decomposition theorem, which shows that every transformatio…
A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra
Mikołaj Bojańczyk, Bartek Klin
-clones are multi-sorted structures that naturally emerge as algebras for infinite trees, just as -semigroups are convenient algebras for infinite words. In the algebraic the…