Estimation of the length of reset words for automata with simple idempotents. (English. Russian original) Zbl 0999.68115
Cybern. Syst. Anal. 36, No. 3, 339-344 (2000); translation from Kibern. Sist. Anal. 2000, No. 3, 32-39 (2000).
Summary: A quadratic upper bound on the length of a minimal reset word is obtained for finite automata with simple idempotents. Each input symbol of the automata considered induces a transformation that is an idempotent with the unit defect or a bijection on the set of states. This bound is only twice as large as the well-known lower bound of this length.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Cerny, J., Poznamka k homogennym experimentom s konecnymy automatami, Mat. Fyz. Cas., SAV, 14, 208-215 (1964) · Zbl 0137.01101 |
| [2] | Pin, J., Sur un cas particulier de la conjecture de Cerny, Lect. Notes Comp. Sci., 62, 345-352 (1978) · Zbl 0389.68036 |
| [3] | Eppstein, D., Reset words for monotonic automata, SIAM J. Comp., 19, 500-510 (1990) · Zbl 0698.68058 · doi:10.1137/0219033 |
| [4] | Rystsov, I., Quasioptimal bound for the length of reset words for regular automata, Acta Cybernetica, 12, 145-152 (1995) · Zbl 0844.68085 |
| [5] | Rystsov, I. K., Rank of a finite automaton, Kibern. Sist. Anal., 3, 3-10 (1992) · Zbl 0875.68658 |
| [6] | Wielandt, H., Finite Permutation Groups (1964), Boston: Academic Press, Boston · Zbl 0138.02501 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
