3 citations · 10 across the 8 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.LO2022★ 2 cited
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…
cs.LO2022
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…