<p>Since this question received no answer for a long time, let me offer a partial answer to the first part of the question:</p>

<blockquote>
  <p>What is known about (minimal) automata recognizing $X^∗$ for a finite code $X$?</p>
</blockquote>

<p>Given a finite set of words $X$, the <em>flower automaton</em> of $X^*$ is the finite nondeterministic
automaton $\mathcal{A} = (Q, A, E, I, F)$, where $Q = \{1, 1\} \cup \{ (u, v)
\in A^+ \times A^+ \mid uv \in X \}$, $I = F = \{(1,1)\}$, with four types
of transitions:
\begin{align*}
 (u, av) &amp;\enspace{\buildrel{a} \over\longrightarrow}\enspace
 (ua, v) \text{ such that } uav \in X,\ (u, v) \neq (1,1) \\
 (u, a) &amp;\enspace{\buildrel{a} \over\longrightarrow}\enspace (1,
 1) \text{ such that } ua \in X,\ u \neq 1  \\
 (1, 1) &amp;\enspace{\buildrel{a}
 \over\longrightarrow}\enspace(a, v) \text{ such that } av \in X,\ v \neq 1\\
 (1, 1) &amp;\enspace{\buildrel{a} \over\longrightarrow}\enspace (1,
 1) \text{ such that } a \in X \bigr\}
\end{align*}
It is easy to see that this automaton recognises $X^*$. For instance, if $A= \{a, b\}$ and $X = \{a, ba, aab, aba\}$, the flower automaton of $X^*$ is the following</p>

<p>$\qquad\qquad\qquad$ <a href="https://i.sstatic.net/sP0tgm.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/sP0tgm.gif" alt="enter image description here"></a></p>

<p>Recall that an automaton is <em>unambiguous</em> if, given two states $p$ and $q$ and a word $w$, there is at most one path from $p$ to $q$ with label $w$. Then the following result holds:</p>

<p><strong>Theorem</strong> [1, Thm 4.2.2]. The set $X$ is a code iff the flower automaton of $X^*$ is unambiguous.</p>

<p>The flower automaton also has an algebraic property which makes it relatively close to the minimal automaton. This property holds for any finite set $X$, but  is easier to state by getting rid of the empty word, that is, by considering a language as a subset of $A^+$ instead of $A^*$.</p>

<p>Recall that a finite semigroup $R$ is <em>locally trivial</em> if, for every idempotent $e \in R$, $eRe = \{e\}$. A morphism $\pi:R \to S$ is <em>locally trivial</em> if for every idempotent $e$ in $S$, the semigroup $\pi^{-1}(e)$ is locally trivial.</p>

<p>The transition semigroup $T$ of the flower automaton of $X^+$ is called the
<em>flower semigroup</em> of $X^+$. Since $T$ recognises $L^+$, there is a surjective morphism $\pi$ from $T$ onto the syntactic semigroup $S$ of $X^+$.</p>

<p><strong>Theorem</strong>. The morphism $\pi:T \to S$ is locally trivial.</p>

<p>An important consequence of this result is that the flower semigroup and the syntactic semigroup have the same number of regular $\mathcal{J}$-classes.</p>

<p><strong>References</strong></p>

<p>[<a href="https://i.sstatic.net/sP0tgm.gif" rel="nofollow noreferrer">1</a>] J. Berstel, D. Perrin, C. Reutenauer, <em>Codes and Automata</em>. Encyclopedia of Mathematics and its Applications, 129. Cambridge University Press, Cambridge, 2010. xiv+619 pp. ISBN: 978-0-521-88831-8</p>

CC BY-SA 3.0
2017-08-08T10:36:16.903Z
2017-08-08T10:36:16.903Z
J.-E. Pin
<p>Let $\Sigma$ be a finite alphabet. A <em>code</em> $X$ over $\Sigma$ is a subset of $\Sigma^*$ such that each word in $X^*$ can be uniquely represented as a concatenation of words in $X$. A code $X$ is <em>finite</em> if $|X|$ is finite. What is known about (minimal) automata recognizing $X^*$ for a finite code $X$? Is there any characterization of such automata (in terms of the structure of the automaton, without knowing $X$)? Is it possible, having such automaton, extract the code $X$ in polynomial time?</p>

<p>I am also interested in these questions when we omit the fact that $X$ is a code, i.e., assume only that $X$ is a finite set of words.</p>

CC BY-SA 3.0
2017-04-15T00:24:19.037Z
What do you want to know about such automata?  It seems that it is easy to construct a DFA for $X^*$ whose size can be easily characterized (it is basically the number of unique prefixes of strings in $X$, and thus is at most the sum of lengths of words in $X$; in particular, it is polynomial size).  Given such a DFA it also seems easy to extract the codewords in $X$ by enumerating all cycles from the start node back to itself.  What specifically are your questions?  What thinking have you already done?  See the "Questions should be based on..." part of our [help/on-topic].
D.W.
CC BY-SA 3.0
2017-04-15T00:38:36.823Z
@D.W., obviously, not all automata have this property. So I ask whether there is a (hopefully, polynomial) characterization of such automata. Also, I don't see how to extract $X$ by enumerating all cycles from the initial state to itself. In fact, there can be an infinite number of cycles, as we can't restrict only to cycles without self-intersections. Can you please be more specific?
Andrew Ryzhikov
CC BY-SA 3.0
2017-04-15T00:54:58.420Z
If I understand correctly, you asked about minimal automata.  I think all minimal DFAs will be isomorphic to the one I described.  If you are asking about all automata, not necessarily minimal, I suggest that you edit the question to clarify.  I don't understand why you can't restrict only to cycles without self-intersections; the prefix-free property means that it is safe to do so, and if $X$ is finite, there will be only finitely many such cycles.  I suggest that you think about the problem for a while, then edit the question to share all the results you've been able to come up with so far.
D.W.
CC BY-SA 3.0
2017-04-16T04:21:57.747Z
Isn't this question the same as the first version of https://cstheory.stackexchange.com/questions/4284/post-correspondence-problem-variant, where $K$ and $K'$ could differ, except that you also ask for the running time?
domotorp
CC BY-SA 3.0
2017-04-16T18:02:36.023Z
@D.W. Consider the code $X = \{a, ab\}$. The minimal automaton of $X^*$ consists of two states $1$, $2$, such that $a$ maps $1$ and $2$ to $2$, and $b$ is undefined for $1$ and maps $2$ to itself. The initial state is $1$, the only accepting state is $2$. The path from the initial to the accepting state labeled $ab$ has a self-intersection.
Andrew Ryzhikov
CC BY-SA 3.0
2017-04-16T18:13:08.723Z
@domotorp Why do you think so? The decision version of the second question in your link is similar to the question of checking whether two languages $A^*$ and $B^*$ have non-empty intersection, but I don't see how the first one is related to my question.
Andrew Ryzhikov
CC BY-SA 3.0
2017-04-16T19:49:27.300Z
OK, so the question (and the answer to it) I linked to shows that there is a PDA that recognizes those $X$ which are codes.
domotorp
CC BY-SA 3.0
2017-04-16T19:58:39.790Z
@domotorp You are right, checking whether a set of words is a code can be done in polynomial time, and it is a quite well-known fact (see ex. http://www-igm.univ-mlv.fr/~berstel/LivreCodes/Codes.html, subsection 0.4). What I want is, having only a minimal automaton recognizing something, check whether this something is a star of a code.
Andrew Ryzhikov
<automata-theory>
Automata recognizing $X^*$ for a finite code $X$
Andrew Ryzhikov
# Automata recognizing $X^*$ for a finite code $X$

(Asked by: username_0 on 2017-04-14)

Let $\Sigma$ be a finite alphabet. A *code* $X$ over $\Sigma$ is a subset of $\Sigma^\*$ such that each word in $X^\*$ can be uniquely represented as a concatenation of words in $X$. A code $X$ is *finite* if $|X|$ is finite. What is known about (minimal) automata recognizing $X^\*$ for a finite code $X$? Is there any characterization of such automata (in terms of the structure of the automaton, without knowing $X$)? Is it possible, having such automaton, extract the code $X$ in polynomial time?

I am also interested in these questions when we omit the fact that $X$ is a code, i.e., assume only that $X$ is a finite set of words.

**Tags:** automata-theory
> **Comments:**
> **username_1**: What do you want to know about such automata?  It seems that it is easy to construct a DFA for $X^*$ whose size can be easily characterized (it is basically the number of unique prefixes of strings in $X$, and thus is at most the sum of lengths of words in $X$; in particular, it is polynomial size).  Given such a DFA it also seems easy to extract the codewords in $X$ by enumerating all cycles from the start node back to itself.  What specifically are your questions?  What thinking have you already done?  See the "Questions should be based on..." part of our [help/on-topic].  
> **username_0**: @D.W., obviously, not all automata have this property. So I ask whether there is a (hopefully, polynomial) characterization of such automata. Also, I don't see how to extract $X$ by enumerating all cycles from the initial state to itself. In fact, there can be an infinite number of cycles, as we can't restrict only to cycles without self-intersections. Can you please be more specific?  
> **username_1**: If I understand correctly, you asked about minimal automata.  I think all minimal DFAs will be isomorphic to the one I described.  If you are asking about all automata, not necessarily minimal, I suggest that you edit the question to clarify.  I don't understand why you can't restrict only to cycles without self-intersections; the prefix-free property means that it is safe to do so, and if $X$ is finite, there will be only finitely many such cycles.  I suggest that you think about the problem for a while, then edit the question to share all the results you've been able to come up with so far.  
> **username_2**: Isn't this question the same as the first version of https://cstheory.stackexchange.com/questions/4284/post-correspondence-problem-variant, where $K$ and $K'$ could differ, except that you also ask for the running time?  
> **username_0**: @D.W. Consider the code $X = \{a, ab\}$. The minimal automaton of $X^*$ consists of two states $1$, $2$, such that $a$ maps $1$ and $2$ to $2$, and $b$ is undefined for $1$ and maps $2$ to itself. The initial state is $1$, the only accepting state is $2$. The path from the initial to the accepting state labeled $ab$ has a self-intersection.  
> **username_0**: @domotorp Why do you think so? The decision version of the second question in your link is similar to the question of checking whether two languages $A^*$ and $B^*$ have non-empty intersection, but I don't see how the first one is related to my question.  
> **username_2**: OK, so the question (and the answer to it) I linked to shows that there is a PDA that recognizes those $X$ which are codes.  
> **username_0**: @domotorp You are right, checking whether a set of words is a code can be done in polynomial time, and it is a quite well-known fact (see ex. http://www-igm.univ-mlv.fr/~berstel/LivreCodes/Codes.html, subsection 0.4). What I want is, having only a minimal automaton recognizing something, check whether this something is a star of a code.  

---

## 1 answers

### Answer by username_3 on 2017-08-08. Score: 2

Since this question received no answer for a long time, let me offer a partial answer to the first part of the question:

> What is known about (minimal) automata recognizing $X^∗$ for a finite code $X$?

Given a finite set of words $X$, the *flower automaton* of $X^\*$ is the finite nondeterministic
automaton $\mathcal{A} = (Q, A, E, I, F)$, where $Q = \{1, 1\} \cup \{ (u, v)
\in A^+ \times A^+ \mid uv \in X \}$, $I = F = \{(1,1)\}$, with four types
of transitions:
\begin{align\*}
(u, av) &\enspace{\buildrel{a} \over\longrightarrow}\enspace
(ua, v) \text{ such that } uav \in X,\ (u, v) \neq (1,1) \\
(u, a) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1,
1) \text{ such that } ua \in X,\ u \neq 1 \\
(1, 1) &\enspace{\buildrel{a}
\over\longrightarrow}\enspace(a, v) \text{ such that } av \in X,\ v \neq 1\\
(1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1,
1) \text{ such that } a \in X \bigr\}
\end{align\*}
It is easy to see that this automaton recognises $X^\*$. For instance, if $A= \{a, b\}$ and $X = \{a, ba, aab, aba\}$, the flower automaton of $X^\*$ is the following

$\qquad\qquad\qquad$ [![enter image description here](https://i.sstatic.net/sP0tgm.gif)](https://i.sstatic.net/sP0tgm.gif)

Recall that an automaton is *unambiguous* if, given two states $p$ and $q$ and a word $w$, there is at most one path from $p$ to $q$ with label $w$. Then the following result holds:

**Theorem** [1, Thm 4.2.2]. The set $X$ is a code iff the flower automaton of $X^\*$ is unambiguous.

The flower automaton also has an algebraic property which makes it relatively close to the minimal automaton. This property holds for any finite set $X$, but is easier to state by getting rid of the empty word, that is, by considering a language as a subset of $A^+$ instead of $A^\*$.

Recall that a finite semigroup $R$ is *locally trivial* if, for every idempotent $e \in R$, $eRe = \{e\}$. A morphism $\pi:R \to S$ is *locally trivial* if for every idempotent $e$ in $S$, the semigroup $\pi^{-1}(e)$ is locally trivial.

The transition semigroup $T$ of the flower automaton of $X^+$ is called the
*flower semigroup* of $X^+$. Since $T$ recognises $L^+$, there is a surjective morphism $\pi$ from $T$ onto the syntactic semigroup $S$ of $X^+$.

**Theorem**. The morphism $\pi:T \to S$ is locally trivial.

An important consequence of this result is that the flower semigroup and the syntactic semigroup have the same number of regular $\mathcal{J}$-classes.

**References**

[[1](https://i.sstatic.net/sP0tgm.gif)] J. Berstel, D. Perrin, C. Reutenauer, *Codes and Automata*. Encyclopedia of Mathematics and its Applications, 129. Cambridge University Press, Cambridge, 2010. xiv+619 pp. ISBN: 978-0-521-88831-8


---

