Conference item icon

Conference item

Geometric decision procedures and the VC dimension of linear arithmetic theories

Abstract:

This paper resolves two open problems on linear integer arithmetic (LIA), also known as Presburger arithmetic. First, we give a triply exponential geometric decision procedure for LIA, i.e., a procedure based on manipulating semilinear sets. This matches the running time of the best quantifier elimination and automata-based procedures. Second, building upon our first result, we give a doubly exponential upper bound on the Vapnik–Chervonenkis (VC) dimension of sets definable in LIA, proving a ...

Expand abstract
Publication status:
Accepted
Peer review status:
Peer reviewed

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St Catherine's College
Role:
Author
Publisher:
Association for Computing Machinery Publisher's website
Host title:
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
Acceptance date:
2022-04-14
Event title:
37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
Event location:
Haifa, Israel
Event website:
https://lics.siglog.org/lics22/
Event start date:
2022-08-02T00:00:00Z
Event end date:
2022-08-05T00:00:00Z
Language:
English
Keywords:
Pubs id:
1264254
Local pid:
pubs:1264254
Deposit date:
2022-06-21

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP