Geodesic
Completely reachable almost group automata
Ural mathematical journal, Tome 10 (2024) no. 2, pp. 37-48 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider finite deterministic automata such that their alphabets consist of exactly one letter of defect 1 and a set of permutations of the state set. We study under which conditions such an automaton is completely reachable. We focus our attention on the case when the set of permutations generates a transitive imprimitive group.
Keywords: Deterministic finite automata, Transition monoid, Complete reachability
Mots-clés : Permutation group 
@article{UMJ_2024_10_2_a3,
     author = {David Fernando Casas Torres},
     title = {Completely reachable almost group automata},
     journal = {Ural mathematical journal},
     pages = {37--48},
     year = {2024},
     volume = {10},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UMJ_2024_10_2_a3/}
}
TY  - JOUR
AU  - David Fernando Casas Torres
TI  - Completely reachable almost group automata
JO  - Ural mathematical journal
PY  - 2024
SP  - 37
EP  - 48
VL  - 10
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UMJ_2024_10_2_a3/
LA  - en
ID  - UMJ_2024_10_2_a3
ER  - 
%0 Journal Article
%A David Fernando Casas Torres
%T Completely reachable almost group automata
%J Ural mathematical journal
%D 2024
%P 37-48
%V 10
%N 2
%U http://geodesic.mathdoc.fr/item/UMJ_2024_10_2_a3/
%G en
%F UMJ_2024_10_2_a3
David Fernando Casas Torres. Completely reachable almost group automata. Ural mathematical journal, Tome 10 (2024) no. 2, pp. 37-48. http://geodesic.mathdoc.fr/item/UMJ_2024_10_2_a3/

[1] Ananichev D., Vorel V., “A new lower bound for reset threshold of binary synchronizing automata with sink”, J. Autom. Lang. Comb., 24:2–4 (2019), 153–164 | DOI | MR | Zbl

[2] André J. M., “Near permutation semigroups”, Semigroups and Languages, 2004, 43–53 | DOI | MR

[3] Berlinkov M. V., Nicaud C., “Synchronizing almost-group automata”, Internat. J. Found. Comput. Sci., 31:08 (2020), 1091–1112 | DOI | MR | Zbl

[4] Bondar E., Casas D., Volkov M., “Completely reachable automata: An interplay between automata, graphs, and trees”, Internat. J. Found. Comput. Sci., 34:06 (2023), 655–690 | DOI | MR | Zbl

[5] Bondar E. A., Volkov M. V., “Completely reachable automata”, Lecture Notes in Comput. Sci.: Descriptional Complexity of Formal Systems (DCFS 2016), v. 9777, eds. C. Câmpeanu, F. Manea, J. Shallit, Springer, Cham:, 2016, 1–17 | DOI | MR | Zbl

[6] Bondar E. A., Volkov M. V., “A characterization of completely reachable automata”, Lecture Notes in Comput. Sci.: Developments in Language Theory (DLT2018), v. 11088, eds. M. Hoshi, S. Seki, Springer, Cham, 2018, 145–155 | DOI | MR | Zbl

[7] Casas D., Volkov M.V., “Binary completely reachable automata”, Lecture Notes in Comput. Sci.: LATIN 2022: Theoretical Informatics, v. 13568, eds. Castañeda A., Rodríguez-Henríquez F., Springer, Cham, 2022, 345–358 | DOI | MR | Zbl

[8] Don H., “The Černý conjecture and 1-contracting automata”, Electron. J. Combin., 23:3 (2016), 3.12 | DOI | MR

[9] Ferens R., Szykulła M., “Completely reachable automata: a polynomial algorithm and quadratic upper bounds”, LIPIcs: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), v. 261, eds. K. Etessami, U. Feige, G. Puppis, Dagstuhl Publishing, Dagstuhl, Germany, 2023, 59:1–59:17 | DOI | MR

[10] Hoffmann S., “New characterizations of primitive permutation groups with applications to synchronizing automata”, Inform. and Comput., 295(A) (2023), 105086 | DOI | MR | Zbl

[11] Maslennikova M.I., Reset Complexity of Ideal Languages, 2014, 12 pp., arXiv: [cs.FL] 1404.2816v1

[12] Rystsov I., “Estimation of the length of reset words for automata with simple idempotents”, Cybernet. Systems Anal., 36:3 (2000), 339–344 | DOI | MR | Zbl

[13] Rystsov I., Szykuła M., Primitive Automata that are Synchronizing, 2023, 13 pp., arXiv: [cs.FL] 2307.01302