# The number of states of local automata

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

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

• something is wrong with your automata, did you forgot certain transitions? The word $abaab$ leads to no state regardless from where I start... – StefanH Jan 16 '14 at 15:32
• 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 Jan 16 '14 at 15:47
• sorry you are right! – StefanH Jan 16 '14 at 16:06
• 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 Jan 16 '14 at 16:13
• 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 Jan 16 '14 at 16:30

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.

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, 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.

• you seem to be implying synchronization delay is equivalent to k-local....? – vzn Feb 6 '14 at 4:12
• 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 Feb 6 '14 at 12:31
• 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 Feb 6 '14 at 16:01
• Ok. I edited the answer to stress the point. I do not think any bridge is needed beyond checking the definition. – Joseph Stack Feb 6 '14 at 16:20
• suggest both defns be stated exactly & then proven to be equivalent. thx for clarification so far. – vzn Feb 6 '14 at 16:28