Zobrazeno 1 - 7
of 7
pro vyhledávání: '"Nathan Lhote"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 18, Issue 3 (2022)
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:
https://doaj.org/article/dc790dc067d24f6e9af81ba90ee9e831
Publikováno v:
Logical Methods in Computer Science, Vol Volume 15, Issue 4 (2019)
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,
Externí odkaz:
https://doaj.org/article/1573398d39d44825b01607fc37bf4daf
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:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7d69026cc7a22238f89206ccc6ed208a
Autor:
Nathan Lhote
Publikováno v:
LICS
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:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::37056f287ef2e61e48096bd9dd7e61f7
http://arxiv.org/abs/2006.16645
http://arxiv.org/abs/2006.16645
Publikováno v:
LICS
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 modelled via an origin function which associates to any position of the outpu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::994bbd40e7fb1afb021117654f6b9193
http://arxiv.org/abs/1701.03670
http://arxiv.org/abs/1701.03670
Decidability of the determinization problem for weighted automata over the semiring $(\mathbb{Z} \cup {-\infty}, \max, +)$, WA for short, is a long-standing open question. We propose two ways of approaching it by constraining the search space of dete
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c63bfad56f03239c27072e636cc5777b
http://arxiv.org/abs/1701.02903
http://arxiv.org/abs/1701.02903
Publikováno v:
LICS
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16)
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16)
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), Jul 2016, New York, United States. pp.387--396, ⟨10.1145/2933575.2934520⟩
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16)
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16)
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), Jul 2016, New York, United States. pp.387--396, ⟨10.1145/2933575.2934520⟩
The algebraic theory of rational languages has provided powerful decidability results. Among them, one of the most fundamental is the definability of a rational language in the class of aperiodic languages, i.e., languages recognized by finite automa
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::aee15eda3320354c20488791bfbaab4d
https://doi.org/10.1145/2933575.2934520
https://doi.org/10.1145/2933575.2934520