[edit]

# Distinguishing Relational Pattern Languages With a Small Number of Short Strings

*Proceedings of The 33rd International Conference on Algorithmic Learning Theory*, PMLR 167:498-514, 2022.

#### Abstract

This paper studies the equivalence problem for relational pattern languages, where a relation imposes dependencies between the two strings with which two variables in a pattern can be replaced simultaneously. Our focus is on the question whether the non-equivalence of two relational patterns is witnessed by short strings, namely those generated by replacing variables in the patterns by strings of length bounded by some (small) number $z$. After establishing a close connection between this problem and the study of the notions of \emph{teaching dimension}\/{and} \emph{no-clash teaching dimension}, we investigate specific classes of relational pattern languages. We show that the smallest number $z$ that serves as a bound for testing equivalence is $2$ when the relation between variable substitutions is that of equal string length, and the alphabet size it at least 3. This has interesting implications on the size and form of non-clashing teaching sets for the corresponding languages. By contrast, not even $z=3$ is sufficient when the constraints require two substituted strings to be the reversal of one another, for alphabets of size 2. We conclude with a negative result on erasing pattern languages.