9
$\begingroup$

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.]

$\endgroup$
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.