Search

• < Previous
• 1
• Next >

---

Quantitative Languages Defined by Functional Automata

Emmanuel Filiot ; Raffaella Gentilini ; Jean-François Raskin.

A weighted automaton is functional if any two accepting runs on the same finite word have the same value. In this paper, we investigate functional weighted automata for four different measures: the sum, the mean, the discounted sum of weights along edges and the ratio between rewards and costs. On&nbsp;[&hellip;]

---

Streamability of nested word transductions

Emmanuel Filiot ; Olivier Gauwin ; Pierre-Alain Reynier ; Frédéric Servais.

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 height bounded memory (HBM) if it can be evaluated with a memory that depends only on the size of T and on the height&nbsp;[&hellip;]

---

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 subclass of aperiodic languages is defined by: counter-free automata, star-free expressions, aperiodic (finite)&nbsp;[&hellip;]

---

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. Specifications are usually modelled as logical formulae or automata over infinite sequences of signals ($\omega$-words), while&nbsp;[&hellip;]

---

Computability of Data-Word Transductions over Different Data Domains

Léo Exibard ; Emmanuel Filiot ; Nathan Lhote ; 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 defined through Turing machines with infinite inputs which can produce the corresponding infinite outputs in the limit. We&nbsp;[&hellip;]

---