<p>A language is <em>$k$-locally testable</em> if it is a Boolean combination of languages of the form $\{u\}$, $vA^*$, $A^*v$ or $A^*wA^*$, with $|u| &lt; k - 1$, $|v| = k - 1$ and $|w| = k$. Thus, yes, $k$-locally testable languages are closed under complementation.</p>

<p>But the link you gave to <a href="http://en.wikipedia.org/wiki/Local_language_%28formal_language%29">Wikipedia</a> gives the definition of <em>local</em> languages, which is not the same thing as <em>locally testable</em> languages.
And indeed, local languages are not closed under complementation.</p>

<p>Finally, a local automaton recognizing a language $L$ might be incomplete. Therefore, you first need to complete it to compute the complement of $L$ by exchanging final and non final states. But this completed automaton is no longer local...</p>

CC BY-SA 3.0
2013-09-17T20:12:53.290Z
thx, clarified a lot. one last remark, hoping I am right. I found another defintion of locality, called *strictly local*. $L$ is called *strictly local* iff there exists a $k$ and a finite set $S \subseteq F_k(?X^*?)$, where $F_k$ denotes the factors of length $k$ in the language, such that $L = \{ w : F_k(?w?) \subseteq S \}$. For $k = 2$ this notion of locality coincides with that of local, because in this case $S := X^2 \setminus F$ (the $F$ from the wikipedia article). The ? denotes some symbol not in $X$, see http://udel.edu/~heinz/talks/Heinz-2011-SLR-slides.pdf
StefanH
CC BY-SA 3.0
2013-09-17T19:46:54.123Z
2013-09-17T19:53:00.247Z
2013-09-17T19:53:00.247Z
J.-E. Pin
<p>Are locally testable languages closed under complementation? I guess yes, because when I can decide membership by sliding a window of size $k$ over the word and looking if the $k$-length words appearing under the window are in a specified set, then deciding the complement is simply looking if some string under the window is not in the set.</p>

<p>The <a href="http://en.wikipedia.org/wiki/Local_language_%28formal_language%29" rel="nofollow">Wikipedia</a> article states that these languages are not closed under complementation. Contrarily, in the paper <a href="http://www.sciencedirect.com/science/article/pii/0304397595001042" rel="nofollow">Local languages and the Berry-Sethi algorithm</a> by J. Berstel &amp; Jean Eric Pin the authors prove that these languages are closed under union, concatenation and Kleene-Star, as opposed to the Wikipedia article. so the Wikipedia information does not seem very trustworthy. Following the proofs in the paper, if I have a local automaton, then the automaton in which the final- and ordinary states are exchanged is still local I think and accepts the complement of the original language. So I think these languages should be closed under complement. Am I right?</p>

CC BY-SA 3.0
2013-09-17T18:31:19.587Z
The paper by Berstel & Pin proves closure under union and concatenation of languages over *disjoint* alphabets (which is what you want for linear rational expressions).
Sylvain
CC BY-SA 3.0
2013-09-17T19:07:18.693Z
Ah, ok thank you. But what about complementation? I am still confused, found the following definition: a language is 2-locally testable iff 1) $W \subseteq \{ e \} \cup X \cup X^2$ or $W$ has the form $V\cdot X^*$, $X^*\cdot V$ or $X^* \cdot V \cdot X^*$ with $V \subseteq \{e\}\cup X\cup X^2$ or 2) there exists 2-locally testable languages $W_1, W_2$ with $W = W_1 \cup W_2$ or $W = X^* \setminus W_1$. According to this definition they should be closed under complement, contrary to wikipedia, http://users.informatik.uni-halle.de/~theo/THEOlehre/AuB/2012/autommAusg2012.pdf
StefanH
<fl.formal-languages><automata-theory>
Closure Properties of Locally Testable Language
StefanH
# Closure Properties of Locally Testable Language

(Asked by: username_0 on 2013-09-17)

Are locally testable languages closed under complementation? I guess yes, because when I can decide membership by sliding a window of size $k$ over the word and looking if the $k$-length words appearing under the window are in a specified set, then deciding the complement is simply looking if some string under the window is not in the set.

The [Wikipedia](http://en.wikipedia.org/wiki/Local_language_%28formal_language%29) article states that these languages are not closed under complementation. Contrarily, in the paper [Local languages and the Berry-Sethi algorithm](http://www.sciencedirect.com/science/article/pii/0304397595001042) by J. Berstel & Jean Eric Pin the authors prove that these languages are closed under union, concatenation and Kleene-Star, as opposed to the Wikipedia article. so the Wikipedia information does not seem very trustworthy. Following the proofs in the paper, if I have a local automaton, then the automaton in which the final- and ordinary states are exchanged is still local I think and accepts the complement of the original language. So I think these languages should be closed under complement. Am I right?

**Tags:** fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: The paper by Berstel & Pin proves closure under union and concatenation of languages over *disjoint* alphabets (which is what you want for linear rational expressions).  
> **username_0**: Ah, ok thank you. But what about complementation? I am still confused, found the following definition: a language is 2-locally testable iff 1) $W \subseteq \{ e \} \cup X \cup X^2$ or $W$ has the form $V\cdot X^*$, $X^*\cdot V$ or $X^* \cdot V \cdot X^*$ with $V \subseteq \{e\}\cup X\cup X^2$ or 2) there exists 2-locally testable languages $W_1, W_2$ with $W = W_1 \cup W_2$ or $W = X^* \setminus W_1$. According to this definition they should be closed under complement, contrary to wikipedia, http://users.informatik.uni-halle.de/~theo/THEOlehre/AuB/2012/autommAusg2012.pdf  

---

## 1 answers

### Answer by username_2 on 2013-09-17. Score: 6 | Accepted answer

A language is *$k$-locally testable* if it is a Boolean combination of languages of the form $\{u\}$, $vA^\*$, $A^\*v$ or $A^\*wA^\*$, with $|u| < k - 1$, $|v| = k - 1$ and $|w| = k$. Thus, yes, $k$-locally testable languages are closed under complementation.

But the link you gave to [Wikipedia](http://en.wikipedia.org/wiki/Local_language_%28formal_language%29) gives the definition of *local* languages, which is not the same thing as *locally testable* languages.
And indeed, local languages are not closed under complementation.

Finally, a local automaton recognizing a language $L$ might be incomplete. Therefore, you first need to complete it to compute the complement of $L$ by exchanging final and non final states. But this completed automaton is no longer local...

> **Comments:**
> **username_0**: thx, clarified a lot. one last remark, hoping I am right. I found another defintion of locality, called *strictly local*. $L$ is called *strictly local* iff there exists a $k$ and a finite set $S \subseteq F_k(?X^*?)$, where $F_k$ denotes the factors of length $k$ in the language, such that $L = \{ w : F_k(?w?) \subseteq S \}$. For $k = 2$ this notion of locality coincides with that of local, because in this case $S := X^2 \setminus F$ (the $F$ from the wikipedia article). The ? denotes some symbol not in $X$, see http://udel.edu/~heinz/talks/Heinz-2011-SLR-slides.pdf  

---

