|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
О задаче минимизации последовательных программ
В. А. Захаровa, Ш. Р. Жайлауоваb a Национальный исследовательский университет "Высшая школа экономики", факультет компьютерных наук, ул. Мясницкая, 20, г. Москва, 101000 Россия
b Московский государственный университет им. М.В. Ломоносова, факультет ВМК, Ленинские горы, д. 1, стр. 52, ГСП-1, Москва, 119991 Россия
Аннотация:
Стандартные схемы программ — это одна из наиболее простых моделей последовательных императивных программ, предназначенная для решения задач оптимизации и верификации программ. Мы рассматриваем разрешимое отношение логико-термальной эквивалентности стандартных схем программ и задачу минимизации их размера при условии сохранения отношения логико-термальной эквивалентности. Нами доказано, что эта задача является алгоритмически разрешимой. Далее показано, что стандартные схемы программ с отношением логико-термальной эквивалентности и конечные детерминированные автоматы-преобразователи, работающие над полугруппами подстановок, взаимно транслируются друг в друга. Отсюда следует, что также разрешимы задачи проверки эквивалентности и минимизации для преобразователей указанного вида. Кроме того, на основе обнаруженной взаимосвязи выделен подкласс стандартных схем программ, минимизация которых осуществима за полиномиальное время при помощи ранее известных методов минимизации автоматов-преобразователей, работающих над полугруппами. В заключении приведен пример, свидетельствующий о том, что в общем случае задача минимизации автоматов-преобразователей над полугруппой подстановок может иметь несколько неизоморфных решений.
Ключевые слова:
последовательная программа, автомат-преобразователь, минимизация, подстановка, полугруппа, эквивалентность.
Поступила в редакцию: 17.07.2017
Образец цитирования:
В. А. Захаров, Ш. Р. Жайлауова, “О задаче минимизации последовательных программ”, Модел. и анализ информ. систем, 24:4 (2017), 415–433
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais574 https://www.mathnet.ru/rus/mais/v24/i4/p415
|
Статистика просмотров: |
Страница аннотации: | 209 | PDF полного текста: | 65 | Список литературы: | 39 |
|