<p>In the article <a href="https://www.irif.fr/~jep/PDF/OmegaSem.pdf" rel="nofollow">Automata and semigroups recognizing infinite words</a> 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 <em>deterministic</em> 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 <em>complete</em> 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:</p>

<p>A path is called initial if its first state is in $I$, a state is called <em>accessible</em> if there exists a initial path to it, and it is called <em>co-accessible</em> if there exists a final path starting at this state. An automaton is called <em>trim</em> if every state is <em>accessible</em> and <em>co-accesible</em>. The above notion of determinism is called <em>local determinism</em>, 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 <em>globally co-deterministic</em> if every word is the label of at most one final path. And it is called <em>locally co-deterministic</em> 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:</p>

<blockquote>
  <p>The local and global notions of co-determinism [...] are equivalent for finite words [page 23]</p>
</blockquote>

<p>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 &amp; \quad \mathrel{\mathop{\rightarrow}^{a}} \quad q_1 \\
 q_0 &amp; \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?</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2016-09-27T11:27:25.453Z
One usually requires having a single final state for co-determinism over finite words.
Sylvain
CC BY-SA 3.0
2016-09-27T12:57:55.140Z
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?
StefanH
CC BY-SA 3.0
2016-09-27T19:17:14.817Z
for instance p. 78 in _Elements of Automata Theory_ by Jacques Sakarovitch, Cambridge University Press, 2009.
Sylvain
CC BY-SA 3.0
2016-09-28T08:06:20.070Z
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?
StefanH
CC BY-SA 3.0
2016-09-29T00:06:13.190Z
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.
Sylvain
<fl.formal-languages><automata-theory><regular-language><nondeterminism>
Why is an automaton on finite words co-deterministic iff its transitions are co-deterministic
StefanH
# Why is an automaton on finite words co-deterministic iff its transitions are co-deterministic

(Asked by: username_0 on 2016-09-27)

In the article [Automata and semigroups recognizing infinite words](https://www.irif.fr/~jep/PDF/OmegaSem.pdf) 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.

**Tags:** fl.formal-languages, automata-theory, regular-language, nondeterminism
> **Comments:**
> **username_1**: One usually requires having a single final state for co-determinism over finite words.  
> **username_0**: 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?  
> **username_1**: for instance p. 78 in _Elements of Automata Theory_ by Jacques Sakarovitch, Cambridge University Press, 2009.  
> **username_0**: 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?  
> **username_1**: 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.  

---

## 0 answers

