RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2010 Number 1, Pages 3–13 (Mi ivm6548)

This article is cited 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.

UDC: 519.713

Received: 27.11.2007


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2010, 54:1, 1–9

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025