VC-dimension of short Presburger formulas
classification
🧮 math.LO
cs.LOmath.CO
keywords
formulaspresburgershortvc-dimensionarithmeticatomsboundedbounds
read the original abstract
We study VC-dimension of short formulas in Presburger Arithmetic, defined to have a bounded number of variables, quantifiers and atoms. We give both lower and upper bounds, which are tight up to a polynomial factor in the bit length of the formula.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.