Zobrazeno 1 - 10
of 129
pro vyhledávání: '"Giovanni Pighizzini"'
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 252, Iss Proc. AFL 2017, Pp 143-156 (2017)
Finite automata whose computations can be reversed, at any point, by knowing the last k symbols read from the input, for a fixed k, are considered. These devices and their accepted languages are called k-reversible automata and k-reversible languages
Externí odkaz:
https://doaj.org/article/a08f1c365e384c3e873cbadcd1a28de8
Autor:
Giovanni Pighizzini
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 90, Iss Proc. AUTOMATA&JAC 2012, Pp 3-20 (2012)
The notion of two-way automata was introduced at the very beginning of automata theory. In 1959, Rabin and Scott and, independently, Shepherdson, proved that these models, both in the deterministic and in the nondeterministic versions, have the same
Externí odkaz:
https://doaj.org/article/e55531e95be0418a90ff0e58a8883cd7
The descriptional complexity of basic operations on regular languages using 1-limited automata, a restricted version of one-tape Turing machines, is investigated. When simulating operations on deterministic finite automata with deterministic 1-limite
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a9e7b139d391c2926be605a05a7df2d1
https://doi.org/10.21203/rs.3.rs-2338203/v1
https://doi.org/10.21203/rs.3.rs-2338203/v1
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
Autor:
Giovanni Pighizzini, Luca Prigioniero
Publikováno v:
Fundamenta Informaticae. 180:103-122
Non-self-embedding grammars are a subclass of context-free grammars which only generate regular languages. The size costs of the conversion of non-self-embedding grammars into equivalent finite automata are studied, by proving optimal bounds for the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::947f1d596fc3185a95639370a7ee56ca
https://doi.org/10.3233/fi-2021-2036
https://doi.org/10.3233/fi-2021-2036
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
Autor:
Giovanni Pighizzini, Luca Prigioniero
Publikováno v:
Information and Computation. 266:60-74
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ec781bad5fc13ef790f2cb150447deef
https://doi.org/10.1016/j.ic.2019.01.002
https://doi.org/10.1016/j.ic.2019.01.002
Publikováno v:
Advancing Research in Information and Communication Technology
Advancing Research in Information and Communication Technology, AICT-600, pp.3-28, 2021, ⟨10.1007/978-3-030-81701-5_1⟩
IFIP Advances in Information and Communication Technology ISBN: 9783030817008
IFIP's Exciting First 60+ Years
Advancing Research in Information and Communication Technology, AICT-600, pp.3-28, 2021, ⟨10.1007/978-3-030-81701-5_1⟩
IFIP Advances in Information and Communication Technology ISBN: 9783030817008
IFIP's Exciting First 60+ Years
part : TC 1: Foundations of Computer Science; International audience; Descriptional complexity has historically been a multidisciplinary area of study, with contributions from automata theory, computational complexity, cryptography, information theor
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::29b065b5d323ec94b2299ddc1bebec39
https://hal.inria.fr/hal-03325981/file/515831_1_En_1_Chapter.pdf
https://hal.inria.fr/hal-03325981/file/515831_1_En_1_Chapter.pdf