COMPLETELY REACHABLE ALMOST GROUP AUTOMATA

David Fernando Casas Torres     (Ural Federal University, 51 Lenina Str., Ekaterimburg, 620000, Russian Federation)

Abstract


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, Permutation group

Full Text:

PDF

References


  1. Ananichev D., Vorel V. A new lower bound for reset threshold of binary synchronizing automata with sink. J. Autom. Lang. Comb., 2019. Vol. 24, No. 2–4. P. 153–164. DOI: 10.25596/jalc-2019-153
  2. André J.M. Near permutation semigroups. Semigroups and Languages, 2004. World Scientific. P. 43–53. DOI: 10.1142/9789812702616_0003
  3. Berlinkov M.V., Nicaud C. Synchronizing almost-group automata. Internat. J. Found. Comput. Sci., 2020. Vol. 31, No. 08. P. 1091–1112. DOI: 10.1142/S0129054120420058
  4. Bondar E., Casas D., Volkov M. Completely reachable automata: An interplay between automata, graphs, and trees. Internat. J. Found. Comput. Sci., 2023. Vol. 34, No. 06. P. 655–690. DOI: 10.1142/S0129054123450053
  5. Bondar E.A., Volkov M.V. Completely reachable automata. In: Lecture Notes in Comput. Sci., vol. 9777: Descriptional Complexity of Formal Systems (DCFS 2016), C. Câmpeanu, F. Manea, J. Shallit (eds). Cham: Springer, 2016. International Publishing. P. 1–17. DOI: 10.1007/978-3-319-41114-9_1
  6.  Bondar E.A., Volkov M.V. A characterization of completely reachable automata. In: Lecture Notes in Comput. Sci., vol. 11088: Developments in Language Theory (DLT2018), M. Hoshi, S. Seki (eds). Cham: Springer, 2018. P. 145–155. DOI: 10.1007/978-3-319-98654-8_12
  7. Casas D., Volkov M.V. Binary completely reachable automata. In: Lecture Notes in Comput. Sci., vol. 13568: LATIN 2022: Theoretical Informatics, Castañeda A., Rodríguez-Henríquez F. (eds). Cham, 2022. Cham: Springer. P. 345–358. DOI: 10.1007/978-3-031-20624-5_21
  8. Don H. The Černý conjecture and 1-contracting automata. Electron. J. Combin., 2016. Vol. 23, No. 3. Art. no. 3.12. DOI: 10.37236/5616
  9. Ferens R., Szykul la M. Completely reachable automata: a polynomial algorithm and quadratic upper bounds. In: LIPIcs, vol. 261: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), K. Etessami, U. Feige, G. Puppis (eds). Dagstuhl, Germany: Dagstuhl Publishing. P. 59:1–59:17. DOI: 10.4230/LIPIcs.ICALP.2023.59
  10. Hoffmann S. New characterizations of primitive permutation groups with applications to synchronizing automata. Inform. and Comput., 2023. Vol. 295(A). Art. no. 105086. DOI: 10.1016/j.ic.2023.105086
  11. Maslennikova M.I. Reset Complexity of Ideal Languages. 2014. 12 p. arXiv:1404.2816v1 [cs.FL]
  12. Rystsov I. Estimation of the length of reset words for automata with simple idempotents. Cybernet. Systems Anal., 2000. Vol. 36, No. 3. P. 339–344. DOI: 10.1007/BF02732984
  13. Rystsov I., Szyku la M. Primitive Automata that are Synchronizing. 2023. 13 p. arXiv:2307.01302v1 [cs.FL]




DOI: http://dx.doi.org/10.15826/umj.2024.2.004

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.