  A separator for two languages is a third language containing the first one
and disjoint from the second one. We investigate the following decision
problem: given two regular input languages, decide whether there exists a
locally testable (resp. a locally threshold testable) separator. In both cases,
we design a decision procedure based on the occurrence of special patterns in
automata accepting the input languages. We prove that the problem is
computationally harder than deciding membership. The correctness proof of the
algorithm yields a stronger result, namely a description of a possible
separator. Finally, we discuss the same problem for context-free input
languages.
