<p>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)$.</p>

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

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

<p>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).</p>

CC BY-SA 3.0
2013-11-22T16:16:22.967Z
2013-11-23T19:52:46.977Z
2013-11-23T19:52:46.977Z
Denis
<p>A language $L$ is called</p>

<p>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 &gt; 0$.</p>

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

<p>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 &gt; 0$ then they are either both in the language or they are both not.</p>

<p>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)</p>

<p>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)?</p>

CC BY-SA 3.0
2013-11-22T18:28:20.960Z
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.
J.-E. Pin
CC BY-SA 3.0
2013-11-24T12:35:11.867Z
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.
StefanH
CC BY-SA 3.0
2013-11-24T13:01:50.240Z
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.
J.-E. Pin
CC BY-SA 3.0
2013-11-24T14:16:04.780Z
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$.
StefanH
<fl.formal-languages><automata-theory>
Difference between locally testable and it's boolean closure
StefanH
# Difference between locally testable and it's boolean closure

(Asked by: username_0 on 2013-11-21)

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)?

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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$.  

---

## 1 answers

### Answer by username_2 on 2013-11-22. Score: 1 | Accepted answer

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


---

