<p>A late answer, but the bound on synchronization delay has been studied for several classes of automata: see for instance <a href="http://link.springer.com/article/10.1007/s11786-007-0027-1">Unambiguous Automata; Béal et al. MCS'08</a>.</p>

<p>In particular; there is a family of deterministic automata that have delay $\Omega(|Q|^2)$ as showed in <a href="http://www.sciencedirect.com/science/article/pii/S030439759880011X#">On the Bound of the Synchronization Delay of a Local Automaton; Béal et al. TCS'98</a>, which matches a corresponding $O(|Q|^2)$ upper bound.</p>

<p>P.S. the synchronization delay defined in the paper is the minimal $k$ for which the deterministic local automaton is $k$-local.</p>

CC BY-SA 3.0
2014-02-06T04:12:00.093Z
you seem to be implying synchronization delay is equivalent to k-local....?
vzn
CC BY-SA 3.0
2014-02-06T12:31:59.047Z
In the TCS'08 paper I quote, for local DFAs
"the synchronization delay is 1+ the length of a longest non-synchronizing sequence", where a non-synchronizing sequence is a word that can lead to two different states. To me, this is by definition the smallest $k$ for which the automaton is $k$-local. Do you think I am mistaken?
Joseph Stack
CC BY-SA 3.0
2014-02-06T16:01:15.310Z
a good answer will not leave out key details. it is possible they are (nearly? exactly?) equivalent but then this would be a new "bridge thm" not in a paper or a published connection...? if so it needs to be fleshed out in more detail somewhere...
vzn
CC BY-SA 3.0
2014-02-06T16:20:43.603Z
Ok. I edited the answer to stress the point. I do not think any bridge is needed beyond checking the definition.
Joseph Stack
CC BY-SA 3.0
2014-02-06T16:28:16.840Z
suggest both defns be stated exactly & then proven to be equivalent. thx for clarification so far.
vzn
CC BY-SA 3.0
2014-02-06T17:19:16.903Z
never heard about sync. delay, thx for pointing out.
StefanH
CC BY-SA 3.0
2014-02-05T13:50:20.780Z
2014-02-06T16:19:07.583Z
2014-02-06T16:19:07.583Z
Joseph Stack
<p>Since you say that $T_w:=\{\delta(q,w):q\in Q\}$ should have <em>at most</em> one element, I'll assume that you use the version of DFA where $\delta$ can be partial. Then this is a counterexample: $X=\{a,b\}, Q=\{0,1,2,3,4\},\delta(q,a)=q+1$ for $q&lt;4$, and $\delta(1,b)=2,\delta(2,b)=3,\delta(4,b)=0$. $F$ and $q_0$ obviously don't matter for this question. </p>

<p>The automaton is $6$-local, but not $5$-local, since $T_{abaab} = \{0,3\}$.</p>

<p>Edit: this counterexample does not work, I'll keep it so that the comments make sense. The following does, though.</p>

<p>Take $X=\{a,b\}, Q=\{0,1,2,3\}$, with transitions $0\to 1(a),1\to 2(a), 2\to 3(a), 2\to 0(b), 3\to 2(b)$. This automaton is $5$-local, but not $4$-local: for $aaba$, we get the paths $0\to 1\to 2\to 0\to 1$ and $1\to 2\to 3\to 2\to 3$, i.e. $T_{aaba}=\{1,3\}$. </p>

CC BY-SA 3.0
2014-01-16T15:32:19.220Z
something is wrong with your automata, did you forgot certain transitions? The word $abaab$ leads to no state regardless from where I start...
StefanH
CC BY-SA 3.0
2014-01-16T15:47:55.980Z
I think it should be correct - stated a bit differently, the transitions are: $0\to 1 (a), 1\to 2 (a,b), 2\to 3 (a,b), 3\to 4(a),$ and $4\to 0(b)$. Then the paths you get for $abaab$ are $0\to 1\to 2\to 3\to 4\to 0$ and $3\to 4\to 0\to 1\to 2\to 3$.
Klaus Draeger
CC BY-SA 3.0
2014-01-16T16:06:44.800Z
sorry you are right!
StefanH
CC BY-SA 3.0
2014-01-16T16:13:21.093Z
Oh, actually I'm not, but for a different reason. You do get those paths, but then you can just repeat $abaab$ indefinitely - this automaton is not $k$-local for any $k$.
Klaus Draeger
CC BY-SA 3.0
2014-01-16T16:30:20.307Z
of course, in general an automata could not be local if there exists two distinct $p,q$ and a word $w$ such that $\delta(p,w) = p$ and $\delta(q,w) = q$.
StefanH
CC BY-SA 3.0
2014-01-16T14:07:51.440Z
2014-01-16T17:56:54.120Z
2014-01-16T17:56:54.120Z
Klaus Draeger
<p>A deterministic automaton $\mathcal A = (X, Q, q_0, F, \delta)$ is called $k$-local  for $k &gt; 0$ if for every $w \in X^k$ the set $\{ \delta(q,w) : q \in Q \}$ contains at most one element. Intuitively that means if a word $w$ of length $k$ leads to a state, then this state is unique, or said differently from an arbitrary word of length $&gt; k$ the last $k$ symbols determine the state it leads to.</p>

<p>Now if an automaton is $k$-local, then it need not be $k'$-local for some $k' &lt; k$, but it has to be $k'$-local for $k' &gt; k$ cause the last symbols of some word $|w| &gt; k$ determine the state, if any, uniquely.</p>

<p>Now I try to connect the number of states and the $k$-localness of an automaton. I conjecture:</p>

<blockquote>
  <p><strong>Lemma:</strong> Let $\mathcal A = (X,Q,q_0,F,\delta)$ be $k$-local, if $|Q| &lt; k$ then the automaton is also $|Q|$-local.</p>
</blockquote>

<p>But I failed to proof, any suggestions or ideas?</p>

<p>I hope by this Lemma to derive something about the number of states of an automaton which is not $k$-local for all $k \le N$ given a fixed $N &gt; 0$, but $k$-local for some $k &gt; N$.</p>

<fl.formal-languages><automata-theory><synchronization>
The number of states of local automata
StefanH
# The number of states of local automata

(Asked by: username_0 on 2014-01-16)

A deterministic automaton $\mathcal A = (X, Q, q\_0, F, \delta)$ is called $k$-local for $k > 0$ if for every $w \in X^k$ the set $\{ \delta(q,w) : q \in Q \}$ contains at most one element. Intuitively that means if a word $w$ of length $k$ leads to a state, then this state is unique, or said differently from an arbitrary word of length $> k$ the last $k$ symbols determine the state it leads to.

Now if an automaton is $k$-local, then it need not be $k'$-local for some $k' < k$, but it has to be $k'$-local for $k' > k$ cause the last symbols of some word $|w| > k$ determine the state, if any, uniquely.

Now I try to connect the number of states and the $k$-localness of an automaton. I conjecture:

> **Lemma:** Let $\mathcal A = (X,Q,q\_0,F,\delta)$ be $k$-local, if $|Q| < k$ then the automaton is also $|Q|$-local.

But I failed to proof, any suggestions or ideas?

I hope by this Lemma to derive something about the number of states of an automaton which is not $k$-local for all $k \le N$ given a fixed $N > 0$, but $k$-local for some $k > N$.

**Tags:** fl.formal-languages, automata-theory, synchronization


---

## 2 answers

### Answer by username_3 on 2014-01-16. Score: 7 | Accepted answer

Since you say that $T\_w:=\{\delta(q,w):q\in Q\}$ should have *at most* one element, I'll assume that you use the version of DFA where $\delta$ can be partial. Then this is a counterexample: $X=\{a,b\}, Q=\{0,1,2,3,4\},\delta(q,a)=q+1$ for $q<4$, and $\delta(1,b)=2,\delta(2,b)=3,\delta(4,b)=0$. $F$ and $q\_0$ obviously don't matter for this question.

The automaton is $6$-local, but not $5$-local, since $T\_{abaab} = \{0,3\}$.

Edit: this counterexample does not work, I'll keep it so that the comments make sense. The following does, though.

Take $X=\{a,b\}, Q=\{0,1,2,3\}$, with transitions $0\to 1(a),1\to 2(a), 2\to 3(a), 2\to 0(b), 3\to 2(b)$. This automaton is $5$-local, but not $4$-local: for $aaba$, we get the paths $0\to 1\to 2\to 0\to 1$ and $1\to 2\to 3\to 2\to 3$, i.e. $T\_{aaba}=\{1,3\}$.

> **Comments:**
> **username_0**: something is wrong with your automata, did you forgot certain transitions? The word $abaab$ leads to no state regardless from where I start...  
> **username_3**: I think it should be correct - stated a bit differently, the transitions are: $0\to 1 (a), 1\to 2 (a,b), 2\to 3 (a,b), 3\to 4(a),$ and $4\to 0(b)$. Then the paths you get for $abaab$ are $0\to 1\to 2\to 3\to 4\to 0$ and $3\to 4\to 0\to 1\to 2\to 3$.  
> **username_0**: sorry you are right!  
> **username_3**: Oh, actually I'm not, but for a different reason. You do get those paths, but then you can just repeat $abaab$ indefinitely - this automaton is not $k$-local for any $k$.  
> **username_0**: of course, in general an automata could not be local if there exists two distinct $p,q$ and a word $w$ such that $\delta(p,w) = p$ and $\delta(q,w) = q$.  

---

### Answer by username_1 on 2014-02-05. Score: 8

A late answer, but the bound on synchronization delay has been studied for several classes of automata: see for instance [Unambiguous Automata; Béal et al. MCS'08](http://link.springer.com/article/10.1007/s11786-007-0027-1).

In particular; there is a family of deterministic automata that have delay $\Omega(|Q|^2)$ as showed in [On the Bound of the Synchronization Delay of a Local Automaton; Béal et al. TCS'98](http://www.sciencedirect.com/science/article/pii/S030439759880011X#), which matches a corresponding $O(|Q|^2)$ upper bound.

P.S. the synchronization delay defined in the paper is the minimal $k$ for which the deterministic local automaton is $k$-local.

> **Comments:**
> **username_2**: you seem to be implying synchronization delay is equivalent to k-local....?  
> **username_1**: In the TCS'08 paper I quote, for local DFAs "the synchronization delay is 1+ the length of a longest non-synchronizing sequence", where a non-synchronizing sequence is a word that can lead to two different states. To me, this is by definition the smallest $k$ for which the automaton is $k$-local. Do you think I am mistaken?  
> **username_2**: a good answer will not leave out key details. it is possible they are (nearly? exactly?) equivalent but then this would be a new "bridge thm" not in a paper or a published connection...? if so it needs to be fleshed out in more detail somewhere...  
> **username_1**: Ok. I edited the answer to stress the point. I do not think any bridge is needed beyond checking the definition.  
> **username_2**: suggest both defns be stated exactly & then proven to be equivalent. thx for clarification so far.  
> **username_0**: never heard about sync. delay, thx for pointing out.  

---

