On Separation by Locally Testable and Locally Threshold Testable Languages

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