Zobrazeno 1 - 10
of 22
pro vyhledávání: '"Bruno Guillon"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 16, Issue 1 (2020)
We prove the undecidability of MSO on $\omega$-words extended with the second-order predicate $U_1(X)$ which says that the distance between consecutive positions in a set $X \subseteq \mathbb{N}$ is unbounded. This is achieved by showing that adding
Externí odkaz:
https://doaj.org/article/b60e87abd5514f09801fab6fe043315b
Publikováno v:
Information and Computation
Information and Computation, 2022, 289 (Part A), pp.104938. ⟨10.1016/j.ic.2022.104938⟩
Information and Computation, 2022, 289 (Part A), pp.104938. ⟨10.1016/j.ic.2022.104938⟩
In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and one-way nondeterministic automata into equivalent two-way deterministic automata. Despite all the attempts, the quest
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c15a579d653965e768d140afa8d253c9
https://hal.science/hal-04093745
https://hal.science/hal-04093745
Publikováno v:
Information and Computation
Information and Computation, 2023, 292, pp.105030. ⟨10.1016/j.ic.2023.105030⟩
Information and Computation, 2023, 292, pp.105030. ⟨10.1016/j.ic.2023.105030⟩
International audience; It is well known that one-tape Turing machines running in linear time are no more powerful than finite automata; namely they recognize exactly the class of regular languages. We prove that it is not decidable if a one-tape mac
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7ebab2a18d86c3f5e0621dea068f10e3
https://doi.org/10.1016/j.ic.2023.105030
https://doi.org/10.1016/j.ic.2023.105030
Publikováno v:
International Journal of Foundations of Computer Science
International Journal of Foundations of Computer Science, 2020, 31 (08), pp.1133-1157. ⟨10.1142/S0129054120420071⟩
International Journal of Foundations of Computer Science, 2020, 31 (08), pp.1133-1157. ⟨10.1142/S0129054120420071⟩
Non-self-embedding grammars are a restriction of context-free grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size from non-self-embedding
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d38940e2b58cb87d40d6368bf14b892c
https://doi.org/10.1142/s0129054120420071
https://doi.org/10.1142/s0129054120420071
Publikováno v:
International Journal of Foundations of Computer Science
International Journal of Foundations of Computer Science, 2022, 33 (3-4), pp.263-284. ⟨10.1142/S0129054122410052⟩
International Journal of Foundations of Computer Science, 2022, 33 (3-4), pp.263-284. ⟨10.1142/S0129054122410052⟩
Finite automata whose computations can be reversed, at any point, by knowing the last [Formula: see text] symbols read from the input, for a fixed [Formula: see text], are considered. These devices and their accepted languages are called [Formula: se
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ffb5fc9762ca3e994a8d1bdf78321af4
https://hal.science/hal-04093709/document
https://hal.science/hal-04093709/document
Publikováno v:
Information and Computation
Information and Computation, 2021, 281, pp.104813. ⟨10.1016/j.ic.2021.104813⟩
Information and Computation, 2021, 281, pp.104813. ⟨10.1016/j.ic.2021.104813⟩
Deterministic pushdown transducers are studied with respect to their ability to compute reversible transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are also backward deterministic and thus
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2c0ab79a408e5344ba5afdbc82774010
https://hal.science/hal-04093721/file/ic-revision.pdf
https://hal.science/hal-04093721/file/ic-revision.pdf
Autor:
Bruno Guillon
Publikováno v:
RAIRO - Theoretical Informatics and Applications. 50:275-294
In a previous paper we showed that two-way (nondeterministic) transducers with unary input and output alphabets have the same recognition power as the sweeping ones. We show that this no longer holds when one of the alphabets has cardinality at least
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::582165bbdfc2338f0962d26060f676ae
https://doi.org/10.1051/ita/2016028
https://doi.org/10.1051/ita/2016028
Publikováno v:
Developments in Language Theory
Developments in Language Theory, pp.366-378, 2018, ⟨10.1007/978-3-319-98654-8_30⟩
Developments in Language Theory ISBN: 9783319986531
DLT
Developments in Language Theory, pp.366-378, 2018, ⟨10.1007/978-3-319-98654-8_30⟩
Developments in Language Theory ISBN: 9783319986531
DLT
It is well-known that one-tape Turing machines working in linear time are no more powerful than finite automata, namely they recognize exactly the class of regular languages. We study the costs, in terms of description sizes, of the conversion of non
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bfe39aab88bfccff1750a009c9a86b49
https://hal.archives-ouvertes.fr/hal-02079083
https://hal.archives-ouvertes.fr/hal-02079083
Publikováno v:
Development of Language Theory
Development of Language Theory, pp.354-365, 2018, ⟨10.1007/978-3-319-98654-8_29⟩
Developments in Language Theory ISBN: 9783319986531
DLT
Development of Language Theory, pp.354-365, 2018, ⟨10.1007/978-3-319-98654-8_29⟩
Developments in Language Theory ISBN: 9783319986531
DLT
Deterministic pushdown transducers are studied with respect to their ability to compute reversible transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are also backward deterministic and thus
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6c9846d42fe77ac0eebf105468b59dd1
https://hal.archives-ouvertes.fr/hal-02079113
https://hal.archives-ouvertes.fr/hal-02079113
Publikováno v:
Implementation and Application of Automata
Implementation and Application of Automata, pp.186-197, 2018, ⟨10.1007/978-3-319-94812-6_16⟩
Implementation and Application of Automata ISBN: 9783319948119
CIAA
Implementation and Application of Automata, pp.186-197, 2018, ⟨10.1007/978-3-319-94812-6_16⟩
Implementation and Application of Automata ISBN: 9783319948119
CIAA
Non-self-embedding grammars are a restriction of context-free grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size from non-self-embedding
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9c17d3f0505a6644fdb3a6ffc30c75b5
https://hal.archives-ouvertes.fr/hal-02079141
https://hal.archives-ouvertes.fr/hal-02079141