In the article Automata and semigroups recognizing infinite words an automaton is specified by $\mathcal A = (Q, A, E, I, F)$ where $I$ is a set of initial states and $F$ a set of final states, $Q$ its state set, $E \subseteq Q\times A \times Q$ the transitions and $A$ its alphabet. It is called deterministic if for every $q \in Q$, $a \in A$ there is at most one state $q' \in Q$ such that $(q, a, q') \in E$ and $|I| = 1$. And it is called complete if there exists at least one $q' \in Q$ such that $(q,a,q') \in E$. Then on page 21 (section 7.1) the following further definitions are made:

A path is called initial if its first state is in $I$, a state is called accessible if there exists a initial path to it, and it is called co-accessible if there exists a final path starting at this state. An automaton is called trim if every state is accessible and co-accesible. The above notion of determinism is called local determinism, and a global notion is defined as $|I| = 1$ and if every word is the label of at most one initial path. Similarly a trim automaton is globally co-deterministic if every word is the label of at most one final path. And it is called locally co-deterministic if all transitions are co-deterministic, which means that we have no two transitions starting in different states, with the same letter that lead to a common state. Then they write:

The local and global notions of co-determinism [...] are equivalent for finite words [page 23]

But what about for example the automaton with three states $q_0, q_1, q_2$, where $q_0$ is initial, $q_1$ and $q_2$ are both final and transitions \begin{align*} q_0 & \quad \mathrel{\mathop{\rightarrow}^{a}} \quad q_1 \\ q_0 & \quad \mathrel{\mathop{\rightarrow}^{a}} \quad q_2. \end{align*} This is not deterministic surely, but it is trim, it is locally co-deterministic but it is not globally co-deterministic as $a$ is the label of two final paths?

So do I interpret these notions wrongly? Why are the global and local notions of co-determinism equivalent for finite words, i.e. an automaton is locally co-deterministic if and only if it is globally co-deterministic on finite words?

I see that for the notions of determinism both variants are equivalent (for finite and for infinite words), but for this equivalence it is crucial that determinism also requires exactly one initial state, but in general we have more than one final state.

  • $\begingroup$ One usually requires having a single final state for co-determinism over finite words. $\endgroup$ – Sylvain Sep 27 '16 at 11:27
  • $\begingroup$ Thats not mentioned in the article, and also not in the book Infinite words by one of the authors. Also this would not make much sense as requiring a single final state would in general alter the class of acceptable languages (in contrary to requiring a single initial state)... but nevertheless do you have any references? $\endgroup$ – StefanH Sep 27 '16 at 12:57
  • $\begingroup$ for instance p. 78 in Elements of Automata Theory by Jacques Sakarovitch, Cambridge University Press, 2009. $\endgroup$ – Sylvain Sep 27 '16 at 19:17
  • $\begingroup$ Okay, thank you. So do you think this might be an error in the article, as this restriction concerning the final states isn't mentioned there? $\endgroup$ – StefanH Sep 28 '16 at 8:06
  • $\begingroup$ The article and the book are about infinite words. I wouldn't call that a mistake; the authors might have assumed the reader to be already familiar with the finite word case. $\endgroup$ – Sylvain Sep 29 '16 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.