Automata recognizing $X^*$ for a finite code $X$ 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.
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) &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

$\qquad\qquad\qquad$ 

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