3 citations · 10 across the 8 of their papers we have counts for
5 papers · 1 filter
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…