5 papers
Expregular functions
Thomas Colcombet, Nathan Lhote, Pierre Ohlmann
Polyregular functions form a robust class of string-to-string functions with polynomial growth, as evidenced by Bojanczyk (2018). This class admits numerous descriptions and enjoys…
Minimizing Streaming String Transducers: An algebraic approach
Yahia Idriss Benalioua, Nathan Lhote, Pierre-Alain Reynier
In this work, we study minimization of rational functions given as appending streaming string transducers (aSST for short). We rely on an algebraic presentation of these functions,…
The structure of polynomial growth for tree automata/transducers and MSO set queries
Paul Gallot, Nathan Lhote, Lê Thà nh Dũng Nguyên
Given an -weighted tree automaton, we give a decision procedure for exponential vs polynomial growth (with respect to the input size) in quadratic time, and an algorith…
Lexicographic transductions of finite words
Emmanuel Filiot, Pierre-Alain Reynier, Nathan Lhote
Regular transductions over finite words have linear input-to-output growth. This class of transductions enjoys many characterizations. Recently, regular transductions have been ext…
Well-Quasi-Orderings on Word Languages
Nathan Lhote, Aliaume Lopez, Lia Schütze
The set of finite words over a well-quasi-ordered set is itself well-quasi-ordered. This seminal result by Higman is a cornerstone of the theory of well-quasi-orderings and has fou…