Erasing Pattern Languages Distinguishable by a Finite Number of Strings

Abstract

Pattern languages have been an object of study in various subfields of computer science for decades. This paper introduces and studies a decision problem on patterns called the finite distinguishability problem: given a pattern $\pi$, are there finite sets $T^+$ and $T^-$ of strings such that the only pattern language containing all strings in $T^+$ and none of the strings in $T^-$ is the language generated by $\pi$? This problem is related to the complexity of teacher-directed learning, as studied in computational learning theory, as well as to the long-standing open question whether the equivalence of two patterns is decidable. We show that finite distinguishability is decidable if the underlying alphabet is of size other than $2$ or $3$, and provide a number of related results, such as (i) partial solutions for alphabet sizes $2$ and $3$, and (ii) decidability proofs for variants of the problem for special subclasses of patterns, namely, regular, 1-variable, and non-cross patterns. For the same subclasses, we further determine the values of two complexity parameters in teacher-directed learning, namely the teaching dimension and the recursive teaching dimension.