О двухленточных машинах, описывающих полугруппы с сокращением.
О двухленточных машинах, описывающих полугруппы с сокращением.
Авторы
Аннотация
Для применения теоретико-автоматного подхода к решению проблемы эквивалентности программ, позволяющего получать эффективно проверяемые достаточные условия функциональной эквивалентности программ. необходимо иметь методы построения детерминированных двухленточных машин, описывающих интерпретацию программных операторов. Во многих приложениях интерпретация программных операторов задается посредством полугрупповых определяющих соотношений (тождеств). В связи с этим нами была исследована задача построения простых детерминированных двухленточных машин, описывающих конечно порожденные полугруппы. Для решения этой задачи предложен алгоритм построения машин указанного вида, описывающих полугруппы с неразложимой единицей, удовлетворяющие условиям левого и правого сокращения. Также установлены достаточные условия, при которых построенная машина является детерминированным двухленточным автоматом с конечным числом состояний.
Издание
Материалы 16-й Международной конференции «Проблемы теоретической кибернетики», Нижний Новгород, 20-25 июня 2011, 2011, Нижегородский государственный университет Нижний Новгород, с. 372-375.
Научная группа
Все публикации за 2011 год
Все публикации