Associação monóide de transição para DFAs

9

Dado um DFA completo , podemos definir uma coleção de funções f a para cada a Γ e com f a : Q Q , f a ( q ) = δ ( q , a ) . Podemos generalizar este conceito a uma palavra w = a 1 , , um m e f wA=(Q,Γ,δ,F)faaΓfa:QQfa(q)=δ(q,a)w=a1,,am ondeindica a composição de função. Além disso, denotamosG={fwwΓ}eGé monóide.fw=fa1famG={fwwΓ}G

[ é geralmente chamado de transição monóide no livro-texto padrão, mas aqui reproduzo a definição para maior clareza.]G

A questão é, dada uma função , podemos decidir f G (idealmente em tempo polinomial), e se esse for o caso (ou seja, existe um w tal que f = f wf:QQfGwf=fw ), se é apenas polinomialmente longo, ou pode ser exponencialmente longo? w

[Acho que essa palavra pode ser exponencialmente longa, mas estou procurando um exemplo simples.]

maomao
fonte

Respostas:

9

Decidability

É decidível. Há apenas um número finito de funções possíveis , para que possa modelar isso como um problema gráfico acessibilidade, com um vértice por função e uma borda g h se existe uma y- tal que h = f umg . Então, testar se uma função g está em G reduz para testar se g é alcançável no gráfico a partir de f ϵ . Você pode encontrar a palavra mais curta usando a primeira vez. O tempo de execução pode ser exponencial em Qf:QQghaΓh=faggGgfϵQ, Apesar.

Comprimento da palavra

A palavra mais curta pode ser exponencialmente longa. Aqui está um exemplo desse DFA. Seja os primeiros k primos. Então um estado terá a forma ( i , x ) em que i { 1 , , k } e x i{ 0 , 1 , , p i - 1 } . Definir um DFA com alfabeto unário Γ = {p1,,pkk(i,x)i{1,,k}xi{0,1,,pi1} e a função de transição δ ( ( i , x ) , 0 = ( i , x + 1 mod p i ) . A função f 0 : Q Q é dada porΓ={0}δ((i,x),0=(i,x+1modpi)f0:QQ

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

Agora considere a função dada porg:QQ

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

É possível utilizar o teorema restante chinês para mostrar que em que n = p 1 × p 2 × × p k - 1 , e que 0 n é o mais curto tal palavra. Além disso, | Q | = P 1 + + p k , de modo que n é exponencialmente grande em Q .g=f0nn=p1×p2××pk10n|Q|=p1++pknQ

Consequentemente, não há esperança para um algoritmo de tempo polinomial que produza essa palavra. Isso ainda deixa em aberto a possibilidade de um algoritmo de tempo polinomial para decidir se está em G , no entanto.gG

DW
fonte