Distinguishing Relational Pattern Languages With a Small Number of Short Strings

Robert C. Holte, S. Mahmoud Mousawi, Sandra Zilles
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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v167-holte22a, title = {Distinguishing Relational Pattern Languages With a Small Number of Short Strings}, author = {Holte, Robert C. and Mousawi, S. Mahmoud and Zilles, Sandra}, booktitle = {Proceedings of The 33rd International Conference on Algorithmic Learning Theory}, pages = {498--514}, year = {2022}, editor = {Dasgupta, Sanjoy and Haghtalab, Nika}, volume = {167}, series = {Proceedings of Machine Learning Research}, month = {29 Mar--01 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v167/holte22a/holte22a.pdf}, url = {https://proceedings.mlr.press/v167/holte22a.html}, 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.} }
Endnote
%0 Conference Paper %T Distinguishing Relational Pattern Languages With a Small Number of Short Strings %A Robert C. Holte %A S. Mahmoud Mousawi %A Sandra Zilles %B Proceedings of The 33rd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Sanjoy Dasgupta %E Nika Haghtalab %F pmlr-v167-holte22a %I PMLR %P 498--514 %U https://proceedings.mlr.press/v167/holte22a.html %V 167 %X 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.
APA
Holte, R.C., Mousawi, S.M. & Zilles, S.. (2022). Distinguishing Relational Pattern Languages With a Small Number of Short Strings. Proceedings of The 33rd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 167:498-514 Available from https://proceedings.mlr.press/v167/holte22a.html.

Related Material