7 citations · 17 across the 16 of their papers we have counts for
4 papers · 1 filter
Equivalence kernels of sequential functions and sequential observation synthesis
Paulin Fournier, Nathan Lhote
We show that one can decide if a rational equivalence relation can be given as the equivalence kernel of a sequential letter-to-letter transduction. This problem comes from the set…
A Robust Class of Linear Recurrence Sequences
Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote +1
We introduce a subclass of linear recurrence sequences which we call poly-rational sequences because they are denoted by rational expressions closed under sum and product. We show…
Synthesis of Computable Regular Functions of Infinite Words
V. Dave, E. Filiot, S. Krishna +1
Regular functions from infinite words to infinite words can be equivalently specified by MSO-transducers, streaming -string transducers as well as deterministic two-way transduc…
String-to-String Interpretations with Polynomial-Size Output
Mikołaj Bojańczyk, Sandra Kiefer, Nathan Lhote
String-to-string MSO interpretations are like Courcelle's MSO transductions, except that a single output position can be represented using a tuple of input positions instead of jus…