УДК 519.713.4

І.К. РИСЦОВ
Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, Україна,
 haryst49@gmail.com

М. ШИКУЛА
Університет Вроцлава, Польща, Вроцлав,
 msz@cs.uni.wroc.pl

ПОРІГ ЗВОРОТНОСТІ ДЛЯ МОНОЇДІВ ПЕРЕТВОРЕНЬ

СПИСОК ЛІТЕРАТУРИ

1. Cerny J., Piricka A., Rosenauerova B. On directable automata. Kybernetica. 1971. Vol. 7, N 4. P. 289–298.


2. Steinberg B. conjecture, synchronizing automata and group representation theory. arXiv:0808.1429v1 [math.CO]. 10 August 2008. https://arxiv.org/abs/0808.1429.


3. Almeida J., Steinberg B. Matrix mortality and the -Pin conjecture. Lecture Notes in Comp. Sci. 2009. Vol. 5583. P. 67–80.


4. Gonze F., Gusev V.V., Gerencser B., Jungers R.M., Volkov M.V. On the interplay between Babai and conjectures. Lecture Notes in Comp. Sci. 2017. Vol. 10396. P. 185–197.


5. Steinberg B. A theory of transformation monoids: Combinatorics and representation theory. Electron. J. Comb. 2010. Vol. 17. Article number R164. https://doi.org/10.37236/436.


6. Araujo J., Cameron P.J., Steinberg B. Between primitive and 2-transitive: Synchronization and its friends. EMS Surveys in Math. Sci. 2017. Vol. 4, N 2. P. 101–184. https://doi.org/ 10.4171/EMSS/4-2-1.


7. Araujo J., Cameron P.J. Primitive groups synchronize non-uniform maps of extreme ranks. J. Combin. Theory Ser. B. 2014. Vol. 106. P 98–114. https://doi.org/10.1016/j.jctb.2014.01.006.


8. Rystsov I. Almost optimal bound of recurrent word length for regular automata. Cybernetics and Systems Analysis. 1995. Vol. 31, N 5. P. 669–674. https://doi.org/10.1007/BF02366314.


9. Bondar E.A., Volkov M.V. Completely reachable automata. Lecture Notes in Comp. Sci. 2016. Vol. 9777. P. 1–17.


10. Bondar E.A., Casas D., Volkov M.V. Completely reachable automata: an interplay between automata, graphs, and trees. arXiv:2201.05075v1 [cs.FL]. https://arxiv.org/abs/2201.05075. 2023. To appear in the International Journal of Foundations of Computer Science.


11. Ferens R., Szykua M. Completely reachable automata: a polynomial algorithm and quadratic upper bounds. Leibniz International Proceedings in Informatics (LIPIcs). 2023. Vol. 261. Article number 59. P. 59:1–59:17. https://doi.org/10.4230/LIPIcs.ICALP.2023.59.


12. Rystsov I., Szykula M. Primitive automata that are synchronizing. arXiv:2307.01302v1 [cs.FL]. 3 July 2023. https://arxiv.org/abs/2307.01302.


13. Rystsov I. Estimation of the length of reset words for automata with simple idempotents. Cybernetics and Systems Analysis. 2000. Vol. 36, N 3. P. 339–344. https://doi.org/10.1007/BF02732984.


14. Rystsov I. Reset words for commutative and solvable automata. Theoretical Computer Science. 1997. Vol. 172, N 1–2. P. 273–279. URL: https://core.ac.uk/download/pdf/82129088.pdf .


15. Howie J.M. Fundamentals of Semigroup Theory. Oxford: Clarendon Press, 1995. 351 p.