7 citations · 17 across the 16 of their papers we have counts for
19 papers
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,…
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…
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…
Minimizing Cost Register Automata over a Field
Yahia Idriss Benalioua, Nathan Lhote, Pierre-Alain Reynier
Weighted automata (WA) are an extension of finite automata that define functions from words to values in a given semiring. An alternative deterministic model, called Cost Register…
Weighted Automata and Expressions over Pre-Rational Monoids
Nicolas Baudru, Louis-Marie Dando, Nathan Lhote +3
The Kleene theorem establishes a fundamental link between automata and expressions over the free monoid. Numerous generalisations of this result exist in the literature. Lifting th…
Computability of Data-Word Transductions over Different Data Domains
Léo Exibard, Emmanuel Filiot, Nathan Lhote +1
In this paper, we investigate the problem of synthesizing computable functions of infinite words over an infinite alphabet (data -words). The notion of computability is defined…
Pebble Minimization of Polyregular Functions
Nathan Lhote
We show that a polyregular word-to-word function is regular if and only if its output size is at most linear in its input size. Moreover a polyregular function can be realized by:…
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…
Edge arboricity : Do we need equitabilility ?
Nathan Lhote, Mohammed Senhaji
In this paper we study a new variant of graph arboricity, which requires all the forests to have the same number of edges (up to a difference of 1). We prove that the new variant,…
Logical and Algebraic Characterizations of Rational Transductions
Emmanuel Filiot, Olivier Gauwin, Nathan Lhote
Rational word languages can be defined by several equivalent means: finite state automata, rational expressions, finite congruences, or monadic second-order (MSO) logic. The robust…
On Delay and Regret Determinization of Max-Plus Automata
Emmanuel Filiot, Ismaël Jecker, Nathan Lhote +2
Decidability of the determinization problem for weighted automata over the semiring , WA for short, is a long-standing open question. We propo…
On Reversible Transducers
Luc Dartois, Paulin Fournier, Ismaël Jecker +1
Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms f…
Logics for Word Transductions with Synthesis
Luc Dartois, Emmanuel Filiot, Nathan Lhote
We introduce a logic, called LT, to express properties of transductions, i.e. binary relations from input to output (finite) words. In LT, the input/output dependencies are modelle…
Towards an algebraic characterization of rational word functions
Nathan Lhote
In formal language theory, several different models characterize regular languages, such as finite automata, congruences of finite index, or monadic second-order logic (MSO). Moreo…