|
Проблемы передачи информации, 1984, том 20, выпуск 1, страницы 74–81
(Mi ppi1123)
|
|
|
|
Теория автоматов
О нижней оценке числа состояний детерминированных целесообразных
автоматов
А. Н. Бойко
Аннотация:
Изучается задача об оценке сложности детерминированных автоматов Мура, целесообразных в однородных марковских средах (ОМС). Мера сложности автомата определяется как число его внутренних состояний. Устанавливается нижняя оценка $N\geq 2k$, числа состояний автоматов, целесообразных в ОМС, улучшающая известную ранее оценку $N>k$ (здесь k – число управлений). Устанавливается нижняя оценка $N\geq k^{3/2}$ числа состояний автоматов, целесообразных в ОМС, при выборе любого их состояния в качестве начального.
Поступила в редакцию: 14.04.1982
Образец цитирования:
А. Н. Бойко, “О нижней оценке числа состояний детерминированных целесообразных
автоматов”, Пробл. передачи информ., 20:1 (1984), 74–81; Problems Inform. Transmission, 20:1 (1984), 56–63
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi1123 https://www.mathnet.ru/rus/ppi/v20/i1/p74
|
Статистика просмотров: |
Страница аннотации: | 158 | PDF полного текста: | 54 |
|