Adhésion monoïde de transition pour les DFA

9

Étant donné un DFA complet A=(Q,Γ,δ,F) , nous pouvons définir une collection de fonctions fa pour chacune aΓ et avec fa:QQ , fa(q)=δ(q,a) . On peut généraliser cette notion à un mot w=a1,,am et fw=fa1fam désigne la composition de la fonction. De plus, nous notonsG={fwwΓ} etG est monoïde.

[ G est généralement appelé transition monoïde dans le manuel standard, mais ici je reproduis la définition pour plus de clarté.]

La question est, étant donné une fonction f:QQ , peut-on décider fG (idéalement en temps polynomial), et si tel est le cas (ie, il existe un w tel que f=fw ), si w est seulement polynomialement longue, ou peut-elle être exponentiellement longue?

[Je suppose qu'en effet un tel mot pourrait être exponentiellement long, mais je cherche un exemple simple.]

maomao
la source

Réponses:

9

Décidabilité

f:QQghaΓh=faggGgfϵQ, bien que.

Longueur du mot

p1,,pkk(i,x)i{1,,k}xi{0,1,,pi1}Γ={0}δ((i,x),0=(i,x+1modpi)f0:QQ

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

Considérons maintenant la fonction donnée parg:QQ

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

Il est possible d'utiliser le théorème du reste chinois pour montrer que où , et que est le plus court de ces mots. Par ailleurs, , de sorte est grand , de manière exponentielle .g=f0nn=p1×p2××pk10n|Q|=p1++pknQ

Par conséquent, il n'y a aucun espoir pour un algorithme à temps polynomial qui produise un tel mot. Cela laisse cependant ouverte la possibilité d'un algorithme polynomial temporel pour décider si est dans , cependant.gG

DW
la source