Zobrazeno 1 - 10
of 59
pro vyhledávání: '"Olivier Finkel"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 15, Issue 2 (2019)
We prove that the B\"uchi topology and the automatic topology are Polish. We also show that this cannot be fully extended to the case of a space of infinite labelled binary trees; in particular the B\"uchi and the Muller topologies are not Polish in
Externí odkaz:
https://doaj.org/article/0e03218d4b124e39b7cdca530d3649be
Autor:
Olivier Finkel
Publikováno v:
Computer Science Journal of Moldova, Vol 15, Iss 1(43), Pp 3-21 (2007)
We give in this paper an example of infinitary rational relation, accepted by a 2-tape Buchi automaton, which is Π30-complete in the Borel hierarchy. Moreover the example of infinitary rational relation given in this paper has a very simple structur
Externí odkaz:
https://doaj.org/article/5a38c78fb4cc4e86b6bdbe00e491f793
Autor:
Olivier Finkel
Publikováno v:
Logical Methods in Computer Science, Vol Volume 10, Issue 3 (2014)
An {\omega}-language is a set of infinite words over a finite alphabet X. We consider the class of recursive {\omega}-languages, i.e. the class of {\omega}-languages accepted by Turing machines with a B\"uchi acceptance condition, which is also the c
Externí odkaz:
https://doaj.org/article/ecb94799b543448184752bee36f55fdf
Autor:
Olivier Finkel
Publikováno v:
Logical Methods in Computer Science, Vol Volume 5, Issue 4 (2009)
We prove the following surprising result: there exist a 1-counter B\"uchi automaton and a 2-tape B\"uchi automaton such that the \omega-language of the first and the infinitary rational relation of the second in one model of ZFC are \pi_2^0-sets, whi
Externí odkaz:
https://doaj.org/article/0a359d8db5e54fedaa7d5103b45e2b77
Autor:
Olivier Finkel, Dominique Lecomte
Publikováno v:
Archive for Mathematical Logic. 60:161-187
We prove that, for any natural number n ≥ 1, we can find a finite alphabet Σ and a finitary language L over Σ accepted by a one-counter automaton, such that the ω-power L ∞ := {w 0 w 1. .. ∈ Σ ω | ∀i ∈ ω w i ∈ L} is Π 0 n-complete.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6a2bce8c25db38d185c8ed7dec3c4014
https://doi.org/10.1007/s00153-020-00737-4
https://doi.org/10.1007/s00153-020-00737-4
Autor:
Olivier Finkel
Publikováno v:
International Journal of Foundations of Computer Science
Language and Automata Theory and Applications
International Journal of Foundations of Computer Science, World Scientific Publishing, 2021, 32 (7), pp.901-920. ⟨10.1142/S0129054121500283⟩
Language and Automata Theory and Applications
International Journal of Foundations of Computer Science, World Scientific Publishing, 2021, 32 (7), pp.901-920. ⟨10.1142/S0129054121500283⟩
We prove two new effective properties of rational functions over infinite words which are realized by finite state Büchi transducers. Firstly, for each such function [Formula: see text], one can construct a deterministic Büchi automaton [Formula: s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4d3b4f95e6500d9ad3ca43ee16acaa92
https://hal.archives-ouvertes.fr/hal-01870467
https://hal.archives-ouvertes.fr/hal-01870467
Autor:
Olivier Finkel, Michał Skrzypczak
Publikováno v:
Fundamenta Informaticae
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2021, 183 (3-4), pp.243-291
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2021, 183 (3-4), pp.243-291
We prove that $\omega$-languages of (non-deterministic) Petri nets and $\omega$-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of $\omega$-languages of (non-determin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6331608ebd7ff89ddbb39cd2a08af775
https://hal.archives-ouvertes.fr/hal-03287498v1/document
https://hal.archives-ouvertes.fr/hal-03287498v1/document
Autor:
Olivier Finkel
Publikováno v:
Language and Automata Theory and Applications ISBN: 9783030406073
LATA
LATA
We prove that ω-regular languages accepted by Buchi or Muller automata satisfy an effective automata-theoretic version of the Baire property. Then we use this result to obtain a new effective property of rational functions over infinite words which
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8b3bcb318c89ba2d1ffa9db9d7e33243
https://doi.org/10.1007/978-3-030-40608-0_21
https://doi.org/10.1007/978-3-030-40608-0_21
Autor:
Olivier Finkel
Publikováno v:
Application and Theory of Petri Nets and Concurrency ISBN: 9783030518301
Petri Nets
Petri Nets
We prove that \(\omega \)-languages of (non-deterministic) Petri nets and \(\omega \)-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of \(\omega \)-languages of (non
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e871c4d5f738973cd89577a868f2bba3
https://doi.org/10.1007/978-3-030-51831-8_4
https://doi.org/10.1007/978-3-030-51831-8_4
Autor:
Jérémie Cabessa, Olivier Finkel
Publikováno v:
Journal of Computer and System Sciences
Journal of Computer and System Sciences, Elsevier, 2019, ⟨10.1016/j.jcss.2018.11.003⟩
Journal of Computer and System Sciences, Elsevier, 2019, ⟨10.1016/j.jcss.2018.11.003⟩
International audience; Analog and evolving recurrent neural networks are super-Turing powerful. Here, we consider analog and evolving neural nets over infinite input streams. We then characterize the topological complexity of their ω-languages as a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cc9cb9c57d7acec1011c3b8e94281e20
https://hal.archives-ouvertes.fr/hal-02318257/document
https://hal.archives-ouvertes.fr/hal-02318257/document