Zobrazeno 1 - 10
of 39
pro vyhledávání: '"Lhote, Nathan"'
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 Automata (CRA), was introduced by Alur et al. It enriches deterministi
Externí odkaz:
http://arxiv.org/abs/2307.13505
Autor:
Baudru, Nicolas, Dando, Louis-Marie, Lhote, Nathan, Monmege, Benjamin, Reynier, Pierre-Alain, Talbot, Jean-Marc
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 this result to a weighted setting has been widely studied. Moreover, dif
Externí odkaz:
http://arxiv.org/abs/2110.12395
Publikováno v:
Logical Methods in Computer Science, Volume 18, Issue 3 (July 29, 2022) lmcs:7104
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 th
Externí odkaz:
http://arxiv.org/abs/2101.07038
Autor:
Lhote, Nathan
Dans la première partie de ce manuscrit nous étudions les fonctions rationnelles, c'est-à-dire définies par des transducteurs unidirectionnels. Notre objectif est d'étendre aux transductions les nombreuses correspondances logique-algèbre qui on
Autor:
Lhote, Nathan
Dans la première partie de ce manuscrit nous étudions les fonctions rationnelles, c'est-à-dire définies par des transducteurs unidirectionnels. Notre objectif est d'étendre aux transductions les nombreuses correspondances logique-algèbre qui on
Externí odkaz:
http://www.theses.fr/2018BORD0185/document
Autor:
Lhote, Nathan
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: a transducer with two pebbles if and only if its output has quadratic
Externí odkaz:
http://arxiv.org/abs/2006.16645
Autor:
Fournier, Paulin, Lhote, Nathan
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 setting of games with imperfect information. In [1, p. 6] the authors pro
Externí odkaz:
http://arxiv.org/abs/1910.06019
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 that this class is robust by giving several characterisations: polynom
Externí odkaz:
http://arxiv.org/abs/1908.03890
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 just a single input position. In particular, the output length is polynom
Externí odkaz:
http://arxiv.org/abs/1905.13190
Publikováno v:
In Information and Computation November 2022 289 Part A