Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1317

Preprint Number 1317

Previous Next Preprint server

1317. Danny Nguyen, Igor Pak
VC-dimension of short Presburger formulas

Submission date: 11 October 2017


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.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 1710.04171: pdf, ps.

Last updated: October 20 2017 12:54 Please send your corrections to: