3
$\begingroup$

Let $L$ be a regular suffix-free language whose complete minimal automaton has $n$ states and that the minimal automaton of $L^R$ has exactly $2^{n-2}+1$ states. Let $p, q$ be two distinct states of the minimal automaton of $L$ which are neither the initial state nor a sink state, then there exists a word $w \in X^*$ such that $\delta(q, w) = \delta(p, w)$ in the minimal automaton for $L$.

That such languages exist is shown in this paper. The above reasoning is used in a paper without any further explanation, and I do not see that it is true. If we denote by $Q = \{0,\ldots, n-1\}$ the states of the minimal automaton of $L$ and by $F$ its final states, where $0$ is the start state and $n-1$ the sink state (which a suffix-free language always has) then it just precedes with constructing a NFA for $L^R$, determinizing by the subset construction and showing that it must contain the $2^{n-2}+1$ sets $\{ \{ 0 \} \}\cup \{ S \subseteq \{1,\ldots, n-2\}\}$ as states. Hence for $p,q \in \{1,\ldots, n-2\}$ we have some $p,q \in S$ such that $\delta_R(F, w) = S$ in the constructed automaton for $L^R$, and then it concludes that $\delta(p, w^R) = r = \delta(q, w^R)$ for some state $r$.

$\endgroup$
  • $\begingroup$ "The above reasoning is used in a paper without any further explanation" -- used in a different paper (please cite) or the paper by Han and Salomaa that you linked to? $\endgroup$ – Aryeh Aug 31 '16 at 19:55
  • $\begingroup$ Its a differenct paper: Complexity of Suffix-free Regular languages by J. Brzozoski and M. Szykula, and the question is related to Theorem 9 of this paper. The paper could be found here: arxiv.org/abs/1504.05159 $\endgroup$ – StefanH Aug 31 '16 at 19:57
  • 1
    $\begingroup$ You could write to Brzozowski... $\endgroup$ – Aryeh Aug 31 '16 at 20:21
  • $\begingroup$ If nobody else can help here... but maybe would be better to have an answer here. $\endgroup$ – StefanH Aug 31 '16 at 21:52
  • $\begingroup$ You already summarize the argument yourself; which step do you find unconvincing? $\endgroup$ – Klaus Draeger Sep 1 '16 at 20:50
3
$\begingroup$

StefanH: You are right, there was this bug in the proof of Theorem 9 in the arxiv version; the argument worked only for $|F|=1$. We fixed this in the revised version for a journal (not published yet) in a similar way you proposed. I have just updated arxiv (https://arxiv.org/abs/1504.05159).

$\endgroup$
2
$\begingroup$

The conclusion that $\delta(p, w^R) = \delta(q, w^R)$ does not seem to hold; but for the argument used in the proof of the paper this is not necessary. More specifically, in the paper it is enough that for every distinct $p,q \in \{1,\ldots, n-2\}$ there is no word $u$ such that $\delta(0, u) = p, \delta(r, u) = q$ for some $r \in \{1,\ldots, n-2\}$.

Suppose the above holds for two $p,q \in \{1,\ldots, n-2\}$ distinct, then as written in the post we have some $S$ with $p,q \in S$ and a word $w$ such that $\delta(F, w) = S$, which gives $\delta(p, w^R) \in F, \delta(q, w^R) \in F$. But then $uw^R \in L$ and furthermore as the automaton is minimal, we have some word $v$ such that $\delta(0,v) = r$, hence $vuw^R \in L$, contradicting the suffix-freeness of $L$.

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