Zobrazeno 1 - 8
of 8
pro vyhledávání: '"Bruno Patrou"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 22 no. 1, Iss Automata, Logic and Semantics (2020)
A monster is an automaton in which every function from states to states is represented by at least one letter. A modifier is a set of functions allowing one to transform a set of automata into one automaton. We revisit some language transformation al
Externí odkaz:
https://doaj.org/article/e07e275edcb34b56a3bd699e19acd64c
Publikováno v:
Developments in Language Theory ISBN: 9783031332630
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::715d481bd2c175ce0464c25b3185699a
https://doi.org/10.1007/978-3-031-33264-7_7
https://doi.org/10.1007/978-3-031-33264-7_7
Publikováno v:
Theoretical Computer Science. 800:15-30
We exhaustively investigate possible combinations of a Boolean operation together with a catenation. In many cases we prove and improve some conjectures by Brzozowski. For each family of operations, we endeavour to provide a common witness with a sma
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::52d29fbbf098e356d3ba30f2d1fc8d55
https://doi.org/10.1016/j.tcs.2019.10.013
https://doi.org/10.1016/j.tcs.2019.10.013
Publikováno v:
Fundamenta Informaticae
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2018, 160 (3), pp.255-279. ⟨10.3233/FI-2018-1683⟩
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2018, 160 (3), pp.255-279. ⟨10.3233/FI-2018-1683⟩
International audience; We improve some results relative to the state complexity of the multiple catenations described by Gao and Yu. In particular we nearly divide by 2 the size of the alphabet needed for witnesses. We also give some refinements to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2baacfb4f1f51a02cd5ece1fba5061d3
https://hal-normandie-univ.archives-ouvertes.fr/hal-02087862
https://hal-normandie-univ.archives-ouvertes.fr/hal-02087862
Publikováno v:
Fundamenta Informaticae. 107:313-330
We formalize the algorithms computing primitive recursive (PR) functions as the abstract state machines (ASMs) whose running length is computable by a PR function. Then we show that there exists a programming language (implementing only PR functions)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::33145da06bef508c5e6bdbf98249294a
https://doi.org/10.3233/fi-2011-405
https://doi.org/10.3233/fi-2011-405
Publikováno v:
CoRR
CoRR, 2015, abs/1505.03474
International Journal of Foundations of Computer Science
International Journal of Foundations of Computer Science, World Scientific Publishing, 2016, 27 (06), pp.675-703. ⟨10.1142/S0129054116500234⟩
CoRR, 2015, abs/1505.03474
International Journal of Foundations of Computer Science
International Journal of Foundations of Computer Science, World Scientific Publishing, 2016, 27 (06), pp.675-703. ⟨10.1142/S0129054116500234⟩
International audience; We study the state complexity of catenation combined with symmetric difference. First, an upper bound is computed using some combinatoric tools. Then, this bound is shown to be tight by giving a witness for it. Moreover, we re
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2d0fa1255b2d81598e09692d4de90a8b
https://hal-normandie-univ.archives-ouvertes.fr/hal-02335276
https://hal-normandie-univ.archives-ouvertes.fr/hal-02335276
Autor:
Bruno Patrou
Publikováno v:
Combinatorics and Computer Science ISBN: 9783540615767
Combinatorics and Computer Science
Combinatorics and Computer Science
We extend the notion of free hull to the zigzag operation in order to build the z-free hulls of a language. We present some properties of those z-free hulls and, specially, we show that a language can have several z-free hulls whereas the free hull i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a95eb28e784ad3a273c519f9d70b68de
https://doi.org/10.1007/3-540-61576-8_88
https://doi.org/10.1007/3-540-61576-8_88