Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №15, Москва, 2006
Авторы: Подловченко Р.И.
Алгебраические модели программ и автоматы
Аннотация:
В этой статье исследуются вопросы сводимости проблем эквивалентности и пустоты для различных классов схем программ и автоматов. Статья состоит из пяти разделов. Вначале приводятся определения основных понятий, относящихся к теории алгебраических моделей программ. В разделе 2 представлен полиномиальный по времени алгоритм проверки эквивалентности схем программ с процедурами в максимальной алгебраической модели программ. В разделе 3 показно, что проблема включения в алгебраической модели программ с процедурами может быть сведена к проблеме включения для одного класса контекстно свободных грамматик. В разделе 4 установлено, что проблема включения для многоленточных автоматов сводима к проблеме эквивалентности схем программ в одном специальном классе алгебраических моделей программ без процедур. Наконец, в разделе 5 описан класс алгебраических моделей программ без процедур и показано, что проблема включения для двухголовочных автоматов сводима к проблеме эквивалентности схем программ в указанном классе алгебраических моделей.
Ключевые слова:
модель программ, схема программ, процедура, контекстно-свободная грамматика, монголенточный автомат, двухголовочный автомат, проблема эквивалентности, проблема включения, сводимость
Язык публикации: русский, страниц: 18 (с. 199-216)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Подловченко Римма Ивановна,  Московский государственный университет им. М.В. Ломоносова, Научно-исследовательский вычислительный центр