7 citations · 17 across the 16 of their papers we have counts for
3 papers · 1 filter
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…
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…