|
Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2010, Number 1, Pages 3–13
(Mi ivm6548)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
The annulation threshold for partially monotonic automata
D. S. Ananichev Chair of Algebra and Discrete Mathematics, Ural State University, Ekaterinburg, Russia
Abstract:
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.
Received: 27.11.2007
Citation:
D. S. Ananichev, “The annulation threshold for partially monotonic automata”, Izv. Vyssh. Uchebn. Zaved. Mat., 2010, no. 1, 3–13; Russian Math. (Iz. VUZ), 54:1 (2010), 1–9
Linking options:
https://www.mathnet.ru/eng/ivm6548 https://www.mathnet.ru/eng/ivm/y2010/i1/p3
|
Statistics & downloads: |
Abstract page: | 470 | Full-text PDF : | 70 | References: | 68 | First page: | 20 |
|