RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2013, том 49, выпуск 2, страницы 58–72 (Mi ppi2108)

Теория автоматов

Детерминизация ординальных автоматов

Ан. А. Мучник


Аннотация: Доказано, что для любого недетерминированного ординального автомата существует детерминированный ординальный автомат, эквивалентный ему для любых счетных ординалов. Количество состояний детерминированного автомата оценивается сверху двойной экспонентой от количества состояний недетерминированного автомата.

УДК: 621.391.1+519.7

Поступила в редакцию: 05.09.2011
После переработки: 05.02.2013


 Англоязычная версия: Problems of Information Transmission, 2013, 49:2, 149–162

Реферативные базы данных:


© МИАН, 2024