9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 center. $\endgroup$ – D.W. Apr 15 '17 at 0:24
  • $\begingroup$ @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? $\endgroup$ – Andrew Ryzhikov Apr 15 '17 at 0:38
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 15 '17 at 0:54
  • $\begingroup$ Isn't this question the same as the first version of cstheory.stackexchange.com/questions/4284/…, where $K$ and $K'$ could differ, except that you also ask for the running time? $\endgroup$ – domotorp Apr 16 '17 at 4:21
  • 1
    $\begingroup$ @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. 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. $\endgroup$ – Andrew Ryzhikov Apr 16 '17 at 19:58
2
$\begingroup$

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

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

$\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.