Conference item
The complexity of Presburger arithmetic with power or powers
- Abstract:
-
We investigate expansions of Presburger arithmetic (Pa), i.e., the theory of the integers with addition and order, with additional structure related to exponentiation: either a function that takes a number to the power of 2, or a predicate 2^ℕ for the powers of 2. The latter theory, denoted Pa(2^ℕ(·)), was introduced by Büchi as a first attempt at characterizing the sets of tuples of numbers that can be expressed using finite automata; Büchi’s method does not give an elementary upper bound, a...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 821.8KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.ICALP.2023.112
Authors
Funding
Bibliographic Details
- Publisher:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Host title:
- 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
- Series:
- Leibniz International Proceedings in Informatics (LIPIcs)
- Volume:
- 261
- Article number:
- 112
- Pages:
- 112:1–112:18
- Publication date:
- 2023-07-05
- Acceptance date:
- 2023-05-01
- Event title:
- 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
- Event location:
- Paderborn, Germany
- Event website:
- https://icalp2023.cs.upb.de/
- Event start date:
- 2023-07-10
- Event end date:
- 2023-07-14
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959772785
Item Description
- Language:
-
English
- Keywords:
- Pubs id:
-
1506028
- Local pid:
-
pubs:1506028
- Deposit date:
-
2023-08-08
Related Items
Terms of use
- Copyright holder:
- Benedikt et al.
- Copyright date:
- 2023
- Rights statement:
- © 2023 Michael Benedikt, Dmitry Chistikov, and Alessio Mansutti; licensed under Creative Commons License CC-BY 4.0.
- 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