5 papers · 1 filter
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…
Polyregular Model Checking
Aliaume Lopez, Rafał Stefański
We introduce a high-level language with Python-like syntax for string-to-string, polyregular, first-order definable transductions. This language features function calls, boolean va…
Monads, Comonads, and Transducers
Rafał Stefański
This paper proposes a definition of recognizable transducers over monads and comonads, which bridges two important ongoing efforts in the current research on regularity. The first…
The single-use restriction for register automata and transducers over infinite alphabets
Rafał Stefański
This thesis studies the single-use restriction for register automata and transducers over infinite alphabets. The restriction requires that a read-access to a register should have…
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…