2
$\begingroup$

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 article states that these languages are not closed under complementation. Contrarily, in the paper Local languages and the Berry-Sethi algorithm 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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Sylvain
    Sep 17, 2013 at 18:31
  • $\begingroup$ 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, users.informatik.uni-halle.de/~theo/THEOlehre/AuB/2012/… $\endgroup$
    – StefanH
    Sep 17, 2013 at 19:07

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 udel.edu/~heinz/talks/Heinz-2011-SLR-slides.pdf $\endgroup$
    – StefanH
    Sep 17, 2013 at 20:12

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.