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