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/}
}
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/