0
$\begingroup$

A language $L$ is called

i) locally testable in the strict sense iff there exists $P, S, I \subseteq X^*$ such that $$ w \in L \mbox{ iff } pref^k(w) \in P, suffix^k(w) \in S, infix^k(w) \subseteq I. $$ for some $k > 0$.

ii) locally testable iff for $u,v \in X^*$ the following holds:

If $pref^k(u) = pref^k(v), suffix^k(u) = suffix^k(v), infix^k(u) = infix^k(v)$ then $$ u \in L \mbox{ iff } v \in L. $$ Meaning if two words coincide in there infixes, suffix and prefix up to a specific length $k > 0$ then they are either both in the language or they are both not.

iii) the class of locally testable events with order is defined as the smallest class of languages containing the locally testable languages and closed under the boolean operations union, intersection and complementation. (this could be equivalently defined with locally testable in the strict sense instead of locally testable)

In what sense do they differ, that iii) contains more languages is clear, for example the language which contains for example $00$ followed by $01$ is in iii) but not in ii) or i) I think (because it involves some kind of order in requiring that $01$ need to follow $00$), but in what sense are ii) and i) different, what is a languge contained in ii) but no in i)?

Improve this question
$\endgroup$
4
  • $\begingroup$ Could you provide us with a reference for these definitions? They do not seem to agree with the standard ones but before suggesting a correction I would like to be sure we speak about the same thing. $\endgroup$
    – J.-E. Pin
    Commented Nov 22, 2013 at 18:28
  • $\begingroup$ The definitions are from the book Counter-free automata by McNaugthon and Papert, which was one of the first who defined these notions. Now after dkuper's answer is is clear to me with these definitions. $\endgroup$
    – StefanH
    Commented Nov 24, 2013 at 12:35
  • $\begingroup$ I don't have access to the book by McNaughton and Papert at the moment, but I do have access to McNaughton's original paper Algebraic Decision Procedures for Local Testability and his definition of strict testability is not yours. In McNaughton's definition, $P, S, I$ are subsets of $X^k$ and not simply of $X^*$ as you stated. $\endgroup$
    – J.-E. Pin
    Commented Nov 24, 2013 at 13:01
  • $\begingroup$ Yes, in there book (opposite to the paper) they don't state explicitly if these sets are from $X^*$ or $X^k$, but I think it makes no difference because $pref^k, suffix^k, infix^k$ yield the prefix,suffix, infixes of length exactly $k$ (but as I see now I did forgot to define them). By the way to cite from the book: "An event is k-testable in the strict sense if there are sets $\alpha, \beta, \gamma$ such that, for all $W$ of length $k$ or more, $W \in \eta$ if and only if $L_k(W) \in \alpha, I_K(W) \subseteq \beta, R_k(W) \in \gamma$" where $L_k, I_k, R_k$ are my $pref^k,suffix^k, infix^k$. $\endgroup$
    – StefanH
    Commented Nov 24, 2013 at 14:16

1 Answer 1

Reset to default
1
$\begingroup$

In ii), you say that $u$ being in $L$ can be deduced only by knowing $pref^k(u)$, $inf^k(u)$ and $suff^k(u)$.

This mean that $L$ can be given by a set $E\subseteq (X^*\times 2^{X^*}\times X^*)$, namely $u\in L$ iff $(pref^k(u),inf^k(u),suff^k(u))\in E$.

The reason why condition i) is stronger is because it forces $E$ to be of the form $P\times 2^I\times S$.

An example of a language which is in ii) but not i) is therefore given by $E=\{ (a,X^*,a), a\in X\}$. This means that $L$ is just the language of words whose last letter is equal to the first. $L$ is locally testable with $k=1$ for condition ii), but it is not for any $k$ for condition i).

Improve this answer
$\endgroup$

Your Answer

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

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