Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-22T16:15:45.535Z Has data issue: false hasContentIssue false
  • English
  • Français

MODEL THEORY AND COMBINATORICS OF BANNED SEQUENCES

Part of: Theory of computing Model theory

Published online by Cambridge University Press:  05 October 2020

HUNTER CHASE  and
JAMES FREITAG
HUNTER CHASE
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF ILLINOIS CHICAGO CHICAGO, IL, USA E-mail: [email protected]
JAMES FREITAG
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF MARYLAND, COLLEGE PARK COLLEGE PARK, MD, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We set up a general context in which one can prove Sauer–Shelah type lemmas. We apply our general results to answer a question of Bhaskar [1] and give a slight improvement to a result of Malliaris and Terry [7]. We also prove a new Sauer–Shelah type lemma in the context of $ \operatorname {\textrm{op}}$ -rank, a notion of Guingona and Hill [4].

Keywords

VC-dimensionLittlestone dimensionstabilityNIPonline learningquery learningPAC learning

MSC classification

Primary: 03C45: Classification theory, stability and related concepts 03C98: Applications of model theory
Secondary: 68Q32: Computational learning theory
Type
Article
Information
The Journal of Symbolic Logic , Volume 87 , Issue 1 , March 2022 , pp. 1 - 20
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bhaskar, S., Thicket density, arXiv preprint, 2017. arXiv:1702.03956.Google Scholar
Chase, H. and Freitag, J., Model theory and machine learning . Bulletin of Symbolic Logic , vol. 25 (2019), pp. 319–332.10.1017/bsl.2018.71CrossRefGoogle Scholar
Chernikov, A., Palacin, D., and Takeuchi, K., On n-dependence, arXiv preprint, 2014. arXiv:1411.0120.Google Scholar
Guingona, V. and Hill, C. D., On a common generalization of Shelah’s 2-rank, dp-rank, and o-minimal dimension . Annals of Pure and Applied Logic , vol. 166 (2015), no. 4, pp. 502–525,10.1016/j.apal.2014.11.007CrossRefGoogle Scholar
Laskowski, M. C., Vapnik-Chervonenkis classes of definable sets . Journal of the London Mathematical Society , vol. 2 (1992), no. 2, pp. 377–384,10.1112/jlms/s2-45.2.377CrossRefGoogle Scholar
Malliaris, M. and Shelah, S., Regularity lemmas for stable graphs . Transactions of the American Mathematical Society , vol. 366 (2014), pp. 1551–1585.10.1090/S0002-9947-2013-05820-5CrossRefGoogle Scholar
Malliaris, M. and Terry, C., On unavoidable induced subgraphs in large prime graphs . Journal of Graph Theory , vol. 88 (2017), 2, pp. 255–270.10.1002/jgt.22209CrossRefGoogle Scholar
Ngo, H. Q., Three proofs of Sauer–Shelah Lemma, Course notes, 2010. Available at https://www.cse.buffalo.edu/hungngo/classes/2010/711/lectures/sauer.pdf.Google Scholar
Simon, P., A Guide to NIP Theories , Cambridge University Press, Cambridge, MA, 2015.10.1017/CBO9781107415133CrossRefGoogle Scholar