Przejście do członkostwa monoidów w DFA

Biorąc pod uwagę pełne DFA $A=(Q, \Gamma, \delta, F)$, możemy zdefiniować zbiór funkcji $f_a$ dla każdego $a\in \Gamma$i z $f_a:Q\rightarrow Q$, $f_a(q)=\delta(q, a)$. Możemy uogólnić to pojęcie na słowo$w=a_1, \cdots, a_m$ i $f_w=f_{a_1}\circ \cdots \circ f_{a_m}$ gdzie $\circ$oznacza skład funkcji. Ponadto oznaczamy$G=\{f_w\mid w\in \Gamma^*\}$ i $G$ jest monoidem.

[$G$jest zwykle nazywany monoidem przejściowym w standardowym podręczniku, ale tutaj odtwarzam definicję dla przejrzystości.]

Pytanie brzmi, biorąc pod uwagę funkcję $f:Q\rightarrow Q$możemy podjąć decyzję $f\in G$ (najlepiej w czasie wielomianowym), a jeśli tak jest (tzn. istnieje $w$ takie, że $f=f_w$), czy $w$ jest tylko wielomianowy, czy może być wykładniczo długi?

[Chyba takie słowo może być wykładniczo długie, ale szukam prostego przykładu.]

Rozstrzygalność

To jest rozstrzygalne. Istnieje tylko wiele możliwych funkcji$f:Q \to Q$, dzięki czemu możesz modelować to jako problem z osiągalnością wykresu, z jednym wierzchołkiem na funkcję i krawędzią $g \to h$ jeśli istnieje $a \in \Gamma$ takie, że $h = f_a \circ g$. Następnie testowanie, czy funkcja$g$ jest w $G$ sprowadza się do sprawdzenia, czy $g$ jest osiągalny na wykresie od $f_\epsilon$. Możesz znaleźć najkrótsze takie słowo przy pierwszym użyciu. Czas działania może być wykładniczy w ciągu$Q$, chociaż.

Długość słowa

Najkrótsze takie słowo może być wykładniczo długie. Oto przykład takiego DFA. Pozwolić$p_1,\dots,p_k$ bądź pierwszy $k$liczby pierwsze Wtedy stan będzie miał formę$(i,x)$ gdzie $i \in \{1,\dots,k\}$ i $x_i \in \{0,1,\dots,p_i-1\}$. Zdefiniuj DFA z jednoargumentowym alfabetem$\Gamma=\{0\}$ i funkcja przejścia $\delta((i,x),0 = (i,x+1 \bmod p_i)$. Funkcja$f_0 :Q \to Q$ jest dany przez

$$f_0(i,x) = (i,x+1 \bmod p_i).$$

Teraz rozważ funkcję $g:Q \to Q$ podane przez

$$g(i,x) = (i,x-1 \bmod p_i).$$

Aby to wykazać, można użyć twierdzenia o reszcie chińskiej $g = f_{0^n}$ gdzie $n=p_1 \times p_2 \times \cdots \times p_k -1$, i to $0^n$jest najkrótszym takim słowem. Co więcej,$|Q|= p_1 + \dots + p_k$, więc $n$ jest wykładniczo duży w $Q$.

W związku z tym nie ma nadziei na algorytm wielomianowy, który generuje takie słowo. To wciąż pozostawia otwartą możliwość algorytmu wielomianowego czasu do decydowania, czy$g$ jest w $G$, chociaż.