10
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

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

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.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.