Conference item
Quantifier elimination for counting extensions of Presburger arithmetic
- Abstract:
-
We give a new quantifier elimination procedure for Presburger arithmetic extended with a unary counting quantifier ∃=xyΦ that binds to the variable x the number of different y satisfying Φ. While our procedure runs in non-elementary time in general, we show that it yields nearly optimal elementary complexity results for expressive counting extensions of Presburger arithmetic, such as the threshold counting quantifier ∃≥cyΦ that requires that the number of different y satisfying Φ be at least ...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 475.4KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-030-99253-8_12
Authors
Funding
Bibliographic Details
- Publisher:
- Springer
- Host title:
- Foundations of Software Science and Computation Structures: FoSSaCS 2022
- Series:
- Lecture Notes in Computer Science
- Series number:
- 13242
- Pages:
- 225-243
- Publication date:
- 2022-03-29
- Acceptance date:
- 2021-12-23
- Event title:
- 25th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2022)
- Event location:
- Munich, Germany
- Event website:
- https://etaps.org/2022/fossacs
- Event start date:
- 2022-04-02
- Event end date:
- 2022-04-07
- DOI:
- EISBN:
- 978-3-030-99253-8
- ISBN:
- 978-3-030-99252-1
Item Description
- Language:
-
English
- Keywords:
- Pubs id:
-
1234399
- Local pid:
-
pubs:1234399
- Deposit date:
-
2022-01-27
Terms of use
- Copyright holder:
- Chistikov et al
- Copyright date:
- 2022
- Rights statement:
- © The Author(s) 2022. Open Access: This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record