13 citations · 38 across the 20 of their papers we have counts for
15 papers · 1 filter
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,…
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…
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…
A robust class of languages of 2-nested words
Séverine Fratani, Guillaume Maurras, Pierre-Alain Reynier
Regular nested word languages (a.k.a. visibly pushdown languages) strictly extend regular word languages, while preserving their main closure and decidability properties. Previous…
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…
Synthesis of Data Word Transducers
Léo Exibard, Emmanuel Filiot, Pierre-Alain Reynier
In reactive synthesis, the goal is to automatically generate an implementation from a specification of the reactive and non-terminating input/output behaviours of a system. Specifi…
Optimal and Robust Controller Synthesis: using Energy Timed Automata with Uncertainty
Giovanni Bacci, Patricia Bouyer, Uli Fahrenberg +3
In this paper, we propose a novel framework for the synthesis of robust and optimal energy-aware controllers. The framework is based on energy timed automata, allowing for easy exp…
Streamability of nested word transductions
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier +1
We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be…
Degree of sequentiality of weighted automata
Laure Daviaud, Ismael Jecker, Pierre-Alain Reynier +1
Weighted automata (WA) are an important formalism to describe quantitative properties. Obtaining equivalent deterministic machines is a longstanding research problem. In this paper…
Two-Way Visibly Pushdown Automata and Transducers
Luc Dartois, Emmanuel Filiot, Pierre-Alain Reynier +1
Automata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently…
Aperiodic String Transducers
Luc Dartois, Ismaël Jecker, Pierre-Alain Reynier
Regular string-to-string functions enjoy a nice triple characterization through deterministic two-way transducers (2DFT), streaming string transducers (SST) and MSO definable funct…
On Streaming String Transducers and HDT0L Systems
Emmanuel Filiot, Pierre-Alain Reynier
Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. Cerny in 2010 as a one-way deterministic automata model to define transformations of fin…
Expressiveness of Visibly Pushdown Transducers
Mathieu Caralp, Emmanuel Filiot, Pierre-Alain Reynier +2
Visibly pushdown transducers (VPTs) are visibly pushdown automata extended with outputs. They have been introduced to model transformations of nested words, i.e. words with a call/…
From Two-Way to One-Way Finite State Transducers
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier +1
Any two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherdson, states t…