Алгоритмы проверки эквивалентности программ с процедурами в прогрессивных полугрупповых перегородчатых моделяхстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 1 апреля 2020 г.
Аннотация:В работе исследуется проблема эквивалентности программ: проверить, имеют ли программы одинаковые (эквивалентные) поведения в заданной модели. Рассматриваемые модели программ с процедурами~--- перегородчатые модели~--- были предложены сравнительно недавно, и для них почти ничего не известно о решении проблемы эквивалентности. В работе предлагается подход к решению проблемы совместного останова программ без процедур, позволяющий с учетом известных результатов обосновать разрешимость и полиномиальную разрешимость проблемы эквивалентности программ с процедурами для многих перегородчатых моделей и построить соответствующие решающие алгоритмы.