13 citations · 38 across the 20 of their papers we have counts for
25 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,…
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…
Synthesis of Robust Optimal Strategies in Weighted Timed Games
Benjamin Monmege, Julie Parreaux, Pierre-Alain Reynier
Weighted Timed Games (WTG for short) are the most widely used model to describe controller synthesis problems involving real-time issues. The synthesized strategies rely on a perfe…
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…
Decidability of One-Clock Weighted Timed Games with Arbitrary Weights
Benjamin Monmege, Julie Parreaux, Pierre-Alain Reynier
Weighted Timed Games (WTG for short) are the most widely used model to describe controller synthesis problems involving real-time issues. Unfortunately, they are notoriously diffic…
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…
Playing Stochastically in Weighted Timed Games to Emulate Memory
Benjamin Monmege, Julie Parreaux, Pierre-Alain Reynier
Weighted timed games are two-player zero-sum games played in a timed automaton equipped with integer weights. We consider optimal reachability objectives, in which one of the playe…
Optimal controller synthesis for timed systems
Damien Busatto-Gaston, Benjamin Monmege, Pierre-Alain Reynier
Weighted timed games are zero-sum games played by two players on a timed automaton equipped with weights, where one player wants to minimise the cumulative weight while reaching a…
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…
Reaching Your Goal Optimally by Playing at Random
Benjamin Monmege, Julie Parreaux, Pierre-Alain Reynier
Shortest-path games are two-player zero-sum games played on a graph equipped with integer weights. One player, that we call Min, wants to reach a target set of states while minimis…
On Computability of Data Word Functions Defined by Transducers
Léo Exibard, Emmanuel Filiot, Pierre-Alain Reynier
In this paper, we investigate the problem of synthesizing computable functions of infinite words over an infinite alphabet (data omega-words). The notion of computability is define…
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…
Sequentiality of String-to-Context Transducers
Pierre-Alain Reynier, Didier Villevalois
Transducers extend finite state automata with outputs, and describe transformations from strings to strings. Sequential transducers, which have a deterministic behaviour regarding…
Symbolic Approximation of Weighted Timed Games
Damien Busatto-Gaston, Benjamin Monmege, Pierre-Alain Reynier
Weighted timed games are zero-sum games played by two players on a timed automaton equipped with weights, where one player wants to minimise the accumulated weight while reaching a…
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…
Optimal Reachability in Divergent Weighted Timed Games
Damien Busatto-Gaston, Benjamin Monmege, Pierre-Alain Reynier
Weighted timed games are played by two players on a timed automaton equipped with weights: one player wants to minimise the accumulated weight while reaching a target, while the ot…
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…