Preview

Труды Института системного программирования РАН

Расширенный поиск

Конечные автоматы в теории алгебраических схем программ

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

Просмотров: 80


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)