Publications > Preprint server > Preprint Number 1603
Preprint Number 1603
1603. Hunter Chase and James Freitag Bounds in Query Learning E-mail: Submission date: 23 April 2019 Abstract: We introduce new combinatorial quantities for concept classes, and prove
lower and upper bounds for learning complexity in several models of query
learning in terms of various combinatorial quantities. Our approach is
flexible
and powerful enough to enough to give new and very short proofs of the
efficient learnability of several prominent examples (e.g. regular languages
and regular $\omega$-languages), in some cases also producing new bounds
on the
number of queries. In the setting of equivalence plus membership queries, we
give an algorithm which learns a class in polynomially many queries whenever
any such algorithm exists. Mathematics Subject Classification: Keywords and phrases: |
Last updated: March 23 2021 09:21 | Please send your corrections to: |