Конечные автоматы в теории алгебраических схем программ
https://doi.org/10.15514/ISPRAS-2015-27(2)-10
Аннотация
Рассматриваемые в этой статье алгебраические модели программ являются обобщением двух моделей программ, введенных в работах А.А. Ляпунова и А.А. Летичевского. Центральное место в теории таких моделей занимает проблема эквивалентности схем программ, заменивших формализованные программы. Доказана разрешимость этой проблемы в широком классе алгебраических моделей программ. Методика получения этого результата восходит к разрешимости проблемы эквивалентности конечных автоматов. Задача статьи состоит в выявлении этого обстоятельства.
Список литературы
1. Подловченко Р.И. Иерархия моделей программ. Программирование, 1981, №2, стр. 3-14.
2. Ляпунов А.А. О логических схемах программ. Проблемы кибернетики. М.: Физматгиз, Вып.1, 1958, cтр. 46-74.
3. Глушков В.М., Летичевский А.А. Теория дискретных преобразователей. Избранные вопросы алгебры и логики. Новосибирск. ИМ СО АН СССР, 1973, cтр. 5-39.
4. Подловченко Р.И. Об одной методике распознавания эквивалентности в алгебраических моделях программ. Программирование, 2011, № 6, c. 33-43.
5. Rabin M.O., Scott D. Finite automata and their decision problems. IBM Journal of Research and Development, 1959, vol.3, №2, p. 114-125.
6. Rutledge J.D. On Ianovs program schemata. Journal of the ACM, 1964, Vol. 11, № 1, p. 1-9.
7. Подловченко Р.И. Эквивалентные преобразования в математических моделях вычислений. Учебное пособие. М.:Издат. отдел факультета ВМиК МГУ им. М.В.Ломоносова. МАКС-Пресс, 2011, 72 с.
8. Подловченко Р.И. О схемах программ с перестановочными и монотонными операторами. Программирование, 2003, №5, cтр. 46-54.
Рецензия
Для цитирования:
Подловченко Р.И. Конечные автоматы в теории алгебраических схем программ. Труды Института системного программирования РАН. 2015;27(2):161-172. https://doi.org/10.15514/ISPRAS-2015-27(2)-10
For citation:
Podlovchenko R.I. Finite state automata in the theory of algebraic program schemata. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(2):161-172. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(2)-10
Послать статью по эл. почте 