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$.
The number of states of local automata
fl.formal languages;automata theory;synchronization
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\}$. 