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

Improve this question
$\endgroup$

2 Answers 2

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

Improve this answer
$\endgroup$
5
  • $\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, 2014 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, 2014 at 15:47
  • $\begingroup$ sorry you are right! $\endgroup$
    – StefanH
    Jan 16, 2014 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, 2014 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, 2014 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ you seem to be implying synchronization delay is equivalent to k-local....? $\endgroup$
    – vzn
    Feb 6, 2014 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, 2014 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, 2014 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, 2014 at 16:20
  • $\begingroup$ suggest both defns be stated exactly & then proven to be equivalent. thx for clarification so far. $\endgroup$
    – vzn
    Feb 6, 2014 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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