|
Известия высших учебных заведений. Математика, 2010, номер 1, страницы 3–13
(Mi ivm6548)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 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$, причем приведенная оценка точна.
Ключевые слова:
синхронизируемый автомат, возвратное слово, частичный автомат, аннулирующее слово.
Поступила: 27.11.2007
Образец цитирования:
Д. С. Ананичев, “Порог аннуляции для частично монотонных автоматов”, Изв. вузов. Матем., 2010, № 1, 3–13; Russian Math. (Iz. VUZ), 54:1 (2010), 1–9
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ivm6548 https://www.mathnet.ru/rus/ivm/y2010/i1/p3
|
Статистика просмотров: |
Страница аннотации: | 455 | PDF полного текста: | 61 | Список литературы: | 52 | Первая страница: | 20 |
|