Learnability of Relatively Quantified Generalized Formulas
Abstract
In this paper we study the learning complexity of a vast class of quantifed formulas called Relatively Quantified Generalized Formulas . This class of formulas is parameterized by a set of predicates, called a basis. We give a complete classification theorem, showing that every basis gives rise to quantified formulas that are either polynomially learnable with equivalence queries, or not polynomially predictable with membership queries under some cryptographic assumption. We also provide a simple criteria distinguishing the learnable cases from the non-learnable cases.
Cite
Text
Bulatov et al. "Learnability of Relatively Quantified Generalized Formulas." International Conference on Algorithmic Learning Theory, 2004. doi:10.1007/978-3-540-30215-5_28Markdown
[Bulatov et al. "Learnability of Relatively Quantified Generalized Formulas." International Conference on Algorithmic Learning Theory, 2004.](https://mlanthology.org/alt/2004/bulatov2004alt-learnability/) doi:10.1007/978-3-540-30215-5_28BibTeX
@inproceedings{bulatov2004alt-learnability,
title = {{Learnability of Relatively Quantified Generalized Formulas}},
author = {Bulatov, Andrei A. and Chen, Hubie and Dalmau, Víctor},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2004},
pages = {365-379},
doi = {10.1007/978-3-540-30215-5_28},
url = {https://mlanthology.org/alt/2004/bulatov2004alt-learnability/}
}