Проверка эквивалентности программ при помощи двухленточных автоматов.

Авторы

Захаров В.А.

Аннотация

Установлены достаточные условия алгоритмической разрешимости проблемы эквивалентности программ, семантика которых определяется на основе моделей динамической логики. Показано, что в том случае, если шкала динамической логики может быть описана двухленточной детерминированной машиной с конечным числом допускающих состояний, то проблема эквивалентности программ, работающих на этой шкале, принадлежит классу сложности NP. В частности, к числу динамической логики относятся шкалы, соответствующие полугруппам без обратимых элементов, обладающим свойством левого сокращения. Если, помимо этого, полугруппа обладает свойством правого сокращения, то проблема эквивалентности программ на шкале, соответствующей такой полугруппе, разрешима за полиномиальное время. В том случае, если шкала динамической логики может быть описана конечным двухленточным автоматом, то проблема эквивалентности программ на такой шкале принадлежит классу сложности NLOGSPACE. Для некоторых классов полугрупп, заданных определяющими соотношениями (тождествами) установлены необходимые и достаточные условия, при которых эти полугруппы могут быть описаны детерминированными двухленточными машинами.

Ключевые слова

программа, эквивалентность, алгоритмическая разрешимость, многоленточный автомат, вычислительная сложность

Издание

Кибернетика и системный анализ, 2010, № 4, с. 39-48.

Научная группа

Теоретическая информатика

Все публикации за 2010 год

Все публикации