Geodesic
The annulation threshold for partially monotonic automata
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2010), pp. 3-13.

Voir la notice de l'article provenant de la source Math-Net.Ru

A deterministic incomplete automaton $\mathscr A=\langle Q,\Sigma,\delta\rangle$ is said to be partially monotonic if its state set $Q$ admits a linear order such that each partial transformation $\delta(\_,a)$ with $a\in\Sigma$ preserves the restriction of the order to the transformation domain. We show that if $\mathscr A$ possesses an annihilating word $w\in\Sigma^*$ whose action is nowhere defined, then $\mathscr A$ is annihilated by a word whose length does not exceed $|Q|+\bigl\lfloor\frac{|Q|-1}2\bigr\rfloor$, and this bound is tight.
Keywords: synchronizable automaton, reset word, partial automaton, annihilating word. 
@article{IVM_2010_1_a1,
     author = {D. S. Ananichev},
     title = {The annulation threshold for partially monotonic automata},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {3--13},
     publisher = {mathdoc},
     number = {1},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2010_1_a1/}
}
TY  - JOUR
AU  - D. S. Ananichev
TI  - The annulation threshold for partially monotonic automata
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2010
SP  - 3
EP  - 13
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2010_1_a1/
LA  - ru
ID  - IVM_2010_1_a1
ER  - 
%0 Journal Article
%A D. S. Ananichev
%T The annulation threshold for partially monotonic automata
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2010
%P 3-13
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2010_1_a1/
%G ru
%F IVM_2010_1_a1
D. S. Ananichev. The annulation threshold for partially monotonic automata. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2010), pp. 3-13. http://geodesic.mathdoc.fr/item/IVM_2010_1_a1/

[1] Černý J., “Poznámka k homogénnym eksperimentom s konečnými automatami”, Mat.-Fyz. Čas. Slovensk. Akad. Vied., 14:3 (1964), 208–215 | MR

[2] Rystsov I., “Reset words for commutative and solvable automata”, Theoret. Comput. Sci., 172:1–2 (1997), 273–279 | DOI | MR | Zbl

[3] Schützenberger M. P., “On finite monoids having only trivial subgroups”, Inf. Control., 8 (1965), 190–194 | DOI | MR | Zbl

[4] Ananichev D. S., Volkov M. V., “Synchronizing generalized monotonic automata”, Theoret. Comput. Sci., 330:1 (2005), 3–13 | DOI | MR | Zbl

[5] Trahtman A. N., “The Černý conjecture for aperiodic automata”, Discrete Math. Theoret. Comput. Sci., 9:2 (2007), 3–10 | MR | Zbl

[6] Volkov M. V., “Synchronizing automata preserving a chain of partial orders”, Lect. Notes Comput. Sci., 4783, 2007, 27–37 | Zbl

[7] Eppstein D., “Reset sequences for monotonic automata”, SIAM J. Comput., 19:3 (1990), 500–510 | DOI | MR | Zbl

[8] Ananichev D. S., Volkov M. V., “Synchronizing monotonic automata”, Theoret. Comput. Sci., 327:3 (2005), 225–239 | DOI | MR