Рассматриваются вопросы восстановления фрагментов входных слов конечных автоматов без потери информации по известным выходным словам (локальное обращение). Показана связь локального обращения автомата из этого класса со свойством синхронизируемости ассоциированного с ним автомата без выхода. Найдены новые классы регистров сдвига с фильтрующими булевыми функциями, допускающих локальное обращение.
Скачать электронную версию публикации
Загружен, раз: 212
- Title О локальной обратимости конечных автоматов без потери информации
- Headline О локальной обратимости конечных автоматов без потери информации
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 39
- Date:
- DOI 10.17223/20710410/39/7
Ключевые слова
конечный автомат, автомат без потери информации, локальная обратимость, регистр сдвига, булева функция, finite state automaton, information lossless automaton, local invertibil-ity, shift registerАвторы
Ссылки
Gecseq F. and Peak I. Algebraic Theory of Automata. Budapest: Akademiai Kiado, 1972. 325 p.
Кудрявцев В. Б., Алешин С. В., Подколзин А. В. Введение в теорию автоматов. М.: Наука, 1985. 316с.
Логачев О. А., Проскурин Г. В., Ященко В. В. Локальное обращение конечного автомата с помощью автоматов // Дискретная математика. 1995. Т. 7. Вып. 2. С. 19-33.
Логачев О. А. О локальной обратимости одного класса булевых отображений // Материалы IX Междунар. семинара «Дискретная математика и ее приложения». Москва, 18-23 июня 2007 г. М.: Изд-во мех.-мат. факультета МГУ, 2007. С. 440-442.
Cerny J. Poznamka k homogennym eksperimentoms konecnymi automatamy. Matematicko-Fizikalny Casopis Slovensk. Akad. Vied. 1964. V. 14. No.3. P.208-216. (in Slovak)
Laemmel A. E. and Rudner B. Study of the Applications of Coding Theory. Report PIBEP-69-034. Politechnic Inst. Brooklyn, N.Y., 1969. 94p.
Клосс Б. Б. Некоторые свойства помехоустойчивых автоматов // Кибернетика. 1988. № 1. С. 10-15.
Рысцов И. К. Возвратные слова для разрешимых автоматов // Кибернетика и системный анализ. 1994. №6. С. 21-26.
Pin J. On two combinatorial problems arising from automata theory // Ann. Discrete Math. 1983. V. 17. P. 535-548.
Volkov M. V. Synchronizing automata and the Cerny conjecture // LNCS. 2008. V. 5196. P.11-27.
Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2010. 384 с.
О локальной обратимости конечных автоматов без потери информации | Прикладная дискретная математика. 2018. № 39. DOI: 10.17223/20710410/39/7
Скачать полнотекстовую версию
Загружен, раз: 595