DOI
10.34229/KCA2522-9664.24.2.3
UDC 519.713.4
1 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
 haryst49@gmail.com
|
2 University of Wroclaw, Faculty of Mathematics and Computer Science, Wroclaw, Poland
msz@cs.uni.wroc.pl
|
RESET THRESHOLDS OF TRANSFORMATION MONOIDS
Abstract. Motivated by the Cerny conjecture for automata, we introduce the concept of monoidal automata,
which allows us the formulation of the Сerny conjecture for monoids.
We obtain upper bounds on the reset threshold of monoids with certain properties.
In particular, we obtain a quadratic upper bound if the transformation monoid contains a primitive group of permutations
and a singular of maximal rank with only one point of contraction.
Keywords: Cerny conjecture, finite automaton, finite monoid, transformation monoid.
full text
REFERENCES
- Cerny J., Piricka A., Rosenauerova B. On directable automata. Kybernetica. 1971. Vol. 7, N 4. P. 289–298.
- Steinberg B. conjecture, synchronizing automata and group representation theory. arXiv:0808.1429v1 [math.CO]. 10 August 2008. https://arxiv.org/abs/0808.1429.
- Almeida J., Steinberg B. Matrix mortality and the -Pin conjecture. Lecture Notes in Comp. Sci. 2009. Vol. 5583. P. 67–80.
- 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.
- 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.
- 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.
- 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.
- 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.
- Bondar E.A., Volkov M.V. Completely reachable automata. Lecture Notes in Comp. Sci. 2016. Vol. 9777. P. 1–17.
- 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.
- 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.
- Rystsov I., Szykula M. Primitive automata that are synchronizing. arXiv:2307.01302v1 [cs.FL]. 3 July 2023. https://arxiv.org/abs/2307.01302.
- 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.
- 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 .
- Howie J.M. Fundamentals of Semigroup Theory. Oxford: Clarendon Press, 1995. 351 p.
