<h2>Decidability</h2>

<p>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.</p>

<h2>Length of the word</h2>

<p>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</p>

<p>$$f_0(i,x) = (i,x+1 \bmod p_i).$$</p>

<p>Now consider the function $g:Q \to Q$ given by</p>

<p>$$g(i,x) = (i,x-1 \bmod p_i).$$</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2017-05-18T00:12:48.713Z
2017-05-18T00:12:48.713Z
D.W.
<p>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. </p>

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

<p>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?  </p>

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

<automata-theory><regular-language><monoid>
Transition monoid membership for DFAs
maomao
# Transition monoid membership for DFAs

(Asked by: username_0 on 2017-05-17)

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

**Tags:** automata-theory, regular-language, monoid


---

## 1 answers

### Answer by username_1 on 2017-05-18. Score: 9

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


---

