|
Прикладная дискретная математика, 2011, номер 2(12), страницы 73–76
(Mi pdm278)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Прикладная теория автоматов
Скелетные автоматы
В. Н. Салий Саратовский государственный университет им. Н. Г. Чернышевского, г. Саратов, Россия
Аннотация:
Автомат (без выходов) называется сильносвязным, если любые два его состояния взаимно достижимы. Скелетный автомат характеризуется противоположным свойством: в нем никакие два различных состояния не являются взаимно достижимыми. Показано, что автомат тогда и только тогда допускает правильную нумерацию состояний, когда он скелетный (теорема 1). Предлагается метод, позволяющий для заданного автомата построить автомат с наименьшим возможным числом состояний, имеющий такую же решетку подавтоматов, при этом полученный автомат оказывается скелетным (теорема 2). Описывается процедура, позволяющая получить из данного автомата скелетный автомат путем удаления (замены петлями) минимального числа дуг в диаграмме переходов исходного автомата.
Ключевые слова:
автомат, сильносвязный автомат, скелетный автомат, правильная нумерация состояний, решетка подавтоматов.
Образец цитирования:
В. Н. Салий, “Скелетные автоматы”, ПДМ, 2011, № 2(12), 73–76
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm278 https://www.mathnet.ru/rus/pdm/y2011/i2/p73
|
Статистика просмотров: |
Страница аннотации: | 308 | PDF полного текста: | 72 | Список литературы: | 40 | Первая страница: | 1 |
|