Erasing Pattern Languages Distinguishable by a Finite Number of Strings
[edit]
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:72108, 2017.
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 teacherdirected learning, as studied in computational learning theory, as well as to the longstanding 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, 1variable, and noncross patterns. For the same subclasses, we further determine the values of two complexity parameters in teacherdirected learning, namely the teaching dimension and the recursive teaching dimension.
Related Material


