Presburger Functional Synthesis: Complexity and Tractable Normal Forms
S. Akshay, A. R. Balasubramanian, Supratik Chakraborty, Georg Zetzsche · 2025
Read Presburger Functional Synthesis: Complexity and Tractable Normal Forms by S. Akshay, A. R. Balasubramanian, Supratik Chakraborty, Georg Zetzsche (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-07207.txt.
Description
Akshay and co-authors present a computer science paper, published in 2025, on automatically building functions that satisfy a logical specification written in Presburger arithmetic. That arithmetic covers whole numbers with addition and order, rich enough for many verification tasks. Functional synthesis asks for an actual function from inputs to outputs that the formula allows, not just a yes or no answer.
The authors show the problem can be solved in exponential time and prove a matching lower bound, an unusually complete answer in this area. For one input and one output the problem is exactly as hard as the Boolean version. They then define a normal form that restores fast, small solutions, and prove how to check and compile specifications into it.
Catalog record
| CREATOR | S. Akshay, A. R. Balasubramanian, Supratik Chakraborty, Georg Zetzsche |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 157 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-07207