Эта публикация цитируется в
2 статьях
Порог аннуляции для частично монотонных автоматов
Д. С. Ананичев Кафедра алгебры и дискретной математики, Уральский государственный университет, г. Екатеринбург
Аннотация:
Детерминированный неполный автомат
$\mathscr A=\langle Q,\Sigma,\delta\rangle$ называется частично монотонным, если на множестве его состояний
$Q$ можно ввести такой линейный порядок, что каждое частичное преобразование
$\delta(\_,a)$, где
$a\in\Sigma$, сохраняет ограничение этого порядка на свою область определения. В работе показано, что если для
$\mathscr A$ найдется какое-либо аннулирующее его слово
$w\in\Sigma^*$, действие которого нигде не определено, то автомат
$\mathscr A$ можно аннулировать словом длины не более
$|Q|+\bigl\lfloor\frac{|Q|-1}2\bigr\rfloor$, причем приведенная оценка точна.
Ключевые слова:
синхронизируемый автомат, возвратное слово, частичный автомат, аннулирующее слово.
УДК:
519.713 Поступила: 27.11.2007