Transition monoid membership for DFAs

Question

Given a complete DFA $A=(Q, \Gamma, \delta, F)$, we can define a collection of functions $f_a$ for each $a\in \Gamma$and with $f_a:Q\rightarrow Q$, $f_a(q)=\delta(q, a)$. We can generalize this notion to a word $w=a_1, \cdots, a_m$ and $f_w=f_{a_1}\circ \cdots \circ f_{a_m}$ where $\circ$ denotes function composition. Furthermore we denote $G=\{f_w\mid w\in \Gamma^*\}$ and $G$ is monoid.

[$G$ is usually called transition monoid in the standard textbook, but here I reproduce the definition for clarity.]

The question is, given a function $f:Q\rightarrow Q$, can we decide $f\in G$ (ideally in polynomial time), and if this is the case (i.e., there exists a $w$ such that $f=f_w$), whether $w$ is only polynomially long, or can be exponentially long?

[I guess that indeed such a word could be exponentially long, but I am looking for a simple example.]

Answer 1

Decidability

It's decidable. There are only finitely many possible functions $f:Q \to Q$, so you can model this as a graph reachability problem, with one vertex per function and an edge $g \to h$ if there exists $a \in \Gamma$ such that $h = f_a \circ g$. Then, testing whether a function $g$ is in $G$ reduces to testing whether $g$ is reachable in the graph from $f_\epsilon$. You can find the shortest such word using breadth-first time. The running time might be exponential in $Q$, though.

Length of the word

The shortest such word might be exponentially long. Here is an example of such a DFA. Let $p_1,\dots,p_k$ be the first $k$ primes. Then a state will be of the form $(i,x)$ where $i \in \{1,\dots,k\}$ and $x_i \in \{0,1,\dots,p_i-1\}$. Define a DFA with unary alphabet $\Gamma=\{0\}$ and the transition function $\delta((i,x),0 = (i,x+1 \bmod p_i)$. The function $f_0 :Q \to Q$ is given by

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

Now consider the function $g:Q \to Q$ given by

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

It is possible to use the Chinese remainder theorem to show that $g = f_{0^n}$ where $n=p_1 \times p_2 \times \cdots \times p_k -1$, and that $0^n$ is the shortest such word. Moreover, $|Q|= p_1 + \dots + p_k$, so $n$ is exponentially large in $Q$.

Consequently, there is no hope for a polynomial-time algorithm that outputs such a word. This still leaves open the possibility of a polynomial time algorithm for deciding whether $g$ is in $G$, though.