3 papers
cs.FL2026
Regularity as seen by Alice and Bob
Omid Yaghoubi, Mikołaj Bojańczyk, Aliaume Lopez +1
The goal of this paper is to propose a unifying model for Nerode-style characterizations of regularity across functions with different output domains. Building on Hauser's work in…
cs.PL2026
Polyregular equivalence is undecidable in higher-order types
Mikołaj Bojańczyk, Grzegorz Fabiański, Rafał Stefański
It is open whether equivalence ( f = g ) is decidable for string-to-string polyregular functions. We consider their higher-order extension based on the λ-calculus definition of pol…
cs.LO2025
Low rank MSO
Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski +2
We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…