• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

О проверке k-значности конечных автоматов-преобразователей над полугруппами

С. 190-192.
Захаров В. А., Джусупекова З. А.

Автоматы-преобразователи в качестве модели последовательных реагирующих программы используются в системном программировании, в компьютерной лингвистике, в криптографии, при проектировании микроэлектронных схем и др. Преобразователь принимает на входе последовательность сигналов и выполняет некоторую последовательность действий, преобразуя тем самым конечные слова входного алфавита в полугрупповое выражение, значения которых и являются результатами вычислений.
 

Мы рассматриваем автоматы-преобразователи над произвольной полугруппой $S$, которая вложима в некоторую конечно порожденную группу с разрешимой проблемой тождества.  Ранее было установлено, что задача проверки $k$-значности конечных автоматов-преобразователей над свободными моноидами разрешима. Затем  было показано, что эту задачу можно решить за время, полиномиальное относительно размера преобразователей и был предложен более общий метод анализа поведения автоматов преобразователей над полугруппами, вложимыми в разрешимые группы,. Однако  применение этого метода было обосновано только для решения задачи проверки 2-значности автоматов-преобразователей. Цель данной работы - показать, что для любого $k, k\geq 1,$ за полиномиальное время проверять свойство $k$-значности конечных автоматов-преобразователей, работающих над полугруппой, вложимой в конечно порожденные разрешимые группы.