Zobrazeno 1 - 10
of 10
pro vyhledávání: '"Giovanna Guaiana"'
Publikováno v:
Lecture Notes in Computer Science
LATA 2019
LATA 2019, Mar 2019, Saint Petersburg, Russia. pp.302-314
Language and Automata Theory and Applications ISBN: 9783030134341
LATA
LATA 2019
LATA 2019, Mar 2019, Saint Petersburg, Russia. pp.302-314
Language and Automata Theory and Applications ISBN: 9783030134341
LATA
We define the geometrical closure of a language over a \(j\)-ary alphabet, and we prove that in the case of dimension 2 the family \(V_{3/2}\) in the Straubing-Therien hierarchy of languages is closed under this operation. In other words, the geometr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::386f225b338a03c70d69ef9a9ae56433
https://hal-normandie-univ.archives-ouvertes.fr/hal-02120309
https://hal-normandie-univ.archives-ouvertes.fr/hal-02120309
Publikováno v:
Information and Computation
Information and Computation, Elsevier, 2013, 230, pp.76-96. ⟨10.1016/j.ic.2013.07.003⟩
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
instname
Information and Computation, Elsevier, 2013, 230, pp.76-96. ⟨10.1016/j.ic.2013.07.003⟩
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
instname
[EN] The closure of a regular language under a [partial] commutation I has been extensively studied. We present new advances on two problems of this area: (1) When is the closure of a regular language under [partial] commutation still regular? (2) Ar
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5f96ed37d1fb23352f5d9cb2f2c01e09
https://doi.org/10.1016/j.ic.2013.07.003
https://doi.org/10.1016/j.ic.2013.07.003
Autor:
Giovanna Guaiana
Publikováno v:
Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2017, 658, pp.175-189. ⟨10.1016/j.tcs.2016.06.023⟩
Theoretical Computer Science, Elsevier, 2017, 658, pp.175-189. ⟨10.1016/j.tcs.2016.06.023⟩
The family of locally testable languages has been extensively studied. We propose an extension of the notion of local testability from the free monoid to the free partially commutative monoid (the so called trace monoid). We show that to formalize th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::322907b27b14265ed4d670a4a5436bbd
https://hal-normandie-univ.archives-ouvertes.fr/hal-02120299
https://hal-normandie-univ.archives-ouvertes.fr/hal-02120299
Publikováno v:
Theoretical Computer Science. 340:432-442
We address the following issue: given a word w ∈ A* and a set of n nonempty words X, how does one determine efficiently whether w ∈ X* or not? We discuss several methods including an O(r × |w| + |X|) algorithm for this problem where r ≤ n is t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::18a9ca5199ee204160be8ddf22437c83
https://doi.org/10.1016/j.tcs.2005.03.030
https://doi.org/10.1016/j.tcs.2005.03.030
Publikováno v:
Theoretical Computer Science. 148:227-260
The problem we mainly deal with is the existence of a coding between two trace monoids. We introduce a new notion of coding: the strong coding (independent letters are mapped into independent traces). We prove that the existence of a strong coding be
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d087a9f23cbdac686a418cc30176021d
https://doi.org/10.1016/0304-3975(95)00036-v
https://doi.org/10.1016/0304-3975(95)00036-v
Publikováno v:
Proceedings of ICALP 2008
ICALP 2008
ICALP 2008, 2008, Reykjavik, Iceland. pp.209-220
Automata, Languages and Programming ISBN: 9783540705826
ICALP (2)
ICALP 2008
ICALP 2008, 2008, Reykjavik, Iceland. pp.209-220
Automata, Languages and Programming ISBN: 9783540705826
ICALP (2)
International audience; The closure of a regular language under commutation or partial commutation has been extensively studied. In this paper, we present new advances on two problems of this area. Problem 1. When is the closure of a regular language
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8b775e3d07530cb7cc877fae70af38b1
https://hal.archives-ouvertes.fr/hal-00340806
https://hal.archives-ouvertes.fr/hal-00340806
Publikováno v:
RAIRO - Theoretical Informatics and Applications. 24:409-417
On construit un treillis associe au comportement de processus concurrents. Les elements de ce treillis sont les sous-graphes bipartis complets d'un graphe biparti. Une application de cette construction est la determination effective de l'automate rec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e2601bade3ca020f888703b66aeee4e4
https://doi.org/10.1051/ita/1990240404091
https://doi.org/10.1051/ita/1990240404091
Publikováno v:
STACS 91 ISBN: 3540537090
STACS
STACS
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::243370a741dd1f76278adb79154e6bfd
https://doi.org/10.1007/bfb0020789
https://doi.org/10.1007/bfb0020789
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783540577850
STACS
STACS
We prove that the existence of a coding between two trace monoids is decidable for some families of trace monoids. Decidability heavily depends on the structure of the dependence graphs. The concept of coding is based on the new notion of strong morp
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8c7c7807585a75c73fdd147984070a7a
https://doi.org/10.1007/3-540-57785-8_154
https://doi.org/10.1007/3-540-57785-8_154
Publikováno v:
Theoretical Computer Science. (2):301-311
Generalizing a classical result of Schutzenberger to free partially commutative monoids, we prove that the family of star-free trace languages coincides with the family of aperiodic trace languages.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7ff1745daf86d3e551a24db5ed8f6e5f