Переход моноидного членства для DFA

9

Учитывая полный DFA A=(Q,Γ,δ,F)мы можем определить коллекцию функций fa для каждого aΓи с fa:QQ, fa(q)=δ(q,a), Мы можем обобщить это понятие на словоw=a1,,am а также fw=fa1fam где обозначает функцию композиции. Кроме того, мы обозначаемG={fwwΓ} а также G является моноидом

[Gобычно называется переходным моноидом в стандартном учебнике, но здесь я привожу определение для ясности.]

Вопрос, учитывая функцию f:QQмы можем решить fG (в идеале за полиномиальное время), и если это так (то есть существует w такой, что f=fw), будь то w является только полиномиально длинной или может быть экспоненциально длинной?

[Я думаю, что действительно такое слово может быть экспоненциально длинным, но я ищу простой пример.]

Maomao
источник

Ответы:

9

Разрешимость

Это разрешимо. Есть только конечное число возможных функцийf:QQ, так что вы можете смоделировать это как проблему достижимости графа, с одной вершиной на функцию и ребром gh если существует aΓ такой, что h=fag, Затем, проверяя, является ли функцияg в G сводится к тестированию g достижим в графе от fϵ, Вы можете найти самое короткое такое слово, используя ширину в первый раз. Время выполнения может быть экспоненциальным вQ, хоть.

Длина слова

Самое короткое такое слово может быть экспоненциально длинным. Вот пример такого DFA. Позволятьp1,,pk быть первым kпростые числа. Тогда состояние будет иметь вид(i,x) где i{1,,k} а также xi{0,1,,pi1}, Определите DFA с одинарным алфавитомΓ={0} и функция перехода δ((i,x),0=(i,x+1modpi), Функцияf0:QQ дан кем-то

f0(i,x)=(i,x+1modpi).

Теперь рассмотрим функцию g:QQ дано

g(i,x)=(i,x1modpi).

Можно использовать теорему об остатках в Китае, чтобы показать, что g=f0n где n=p1×p2××pk1и что 0nсамое короткое такое слово. Более того,|Q|=p1++pk, так n экспоненциально велик в Q,

Следовательно, нет никакой надежды на алгоритм полиномиального времени, который выводит такое слово. Это все еще оставляет открытой возможность использования алгоритма полиномиального времени дляg в G, хоть.

DW
источник