Cover Image

The complexity of Presburger arithmetic with power or powers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Benedikt, Michael, Chistikov, Dmitry, Mansutti, Alessio
Format:	Preprint
Published:	2023
Subjects:	Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Integer Linear-Exponential Programming in NP by Quantifier Elimination
by: Chistikov, Dmitry, et al.
Published: (2024)

One-Parametric Presburger Arithmetic has Quantifier Elimination
by: Mansutti, Alessio, et al.
Published: (2025)

How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
by: Benedikt, Michael, et al.
Published: (2026)

An efficient quantifier elimination procedure for Presburger arithmetic
by: Haase, Christoph, et al.
Published: (2024)

On Presburger arithmetic extended with non-unary counting quantifiers
by: Habermehl, Peter, et al.
Published: (2022)

Unary counting quantifiers do not increase the expressive power of Presburger aritmetic: an alternative shorter proof
by: Choffrut, Christian
Published: (2024)

Intersecting Dense Automata
by: Chistikov, Dmitry, et al.
Published: (2026)

Analysis of logics with arithmetic
by: Benedikt, Michael, et al.
Published: (2025)

On the Decidability of Presburger Arithmetic Expanded with Powers
by: Karimov, Toghrul, et al.
Published: (2024)

Optimization Modulo Integer Linear-Exponential Programs
by: Hitarth, S, et al.
Published: (2025)

On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number
by: Gallego-Hernández, Jorge, et al.
Published: (2025)

On Polynomial-Time Decidability of k-Negations Fragments of First-Order Theories
by: Haase, Christoph, et al.
Published: (2024)

On two-variable guarded fragment logic with expressive local Presburger constraints
by: Lu, Chia-Hsuan, et al.
Published: (2022)

MCSAT Modulo Transcendental Arithmetics
by: Gallego-Hernández, Jorge, et al.
Published: (2026)

Invariants for One-Counter Automata with Disequality Tests
by: Chistikov, Dmitry, et al.
Published: (2024)

Presburger Functional Synthesis: Complexity and Tractable Normal Forms
by: Akshay, S., et al.
Published: (2025)

Embedded Finite Models Beyond Restricted Quantifier Collapse
by: Benedikt, Michael, et al.
Published: (2023)

Decidability of extensions of Presburger arithmetic by generalised polynomials
by: Konieczny, Jakub
Published: (2024)

On the expressive power of inquisitive team logic and inquisitive first-order logic
by: Kontinen, Juha, et al.
Published: (2026)

On matrix rank function over bounded arithmetics
by: Ken, Eitetsu, et al.
Published: (2023)

Wadge degrees of $Δ^0_2$ omega-powers
by: Finkel, Olivier, et al.
Published: (2024)

From learnable objects to learnable random objects
by: Anderson, Aaron, et al.
Published: (2025)

The Tractability Border of Reachability in Simple Vector Addition Systems with States
by: Chistikov, Dmitry, et al.
Published: (2024)

QBF Merge Resolution is powerful but unnatural
by: Mahajan, Meena, et al.
Published: (2022)

Tighter Bounds for Query Answering with Guarded TGDs
by: Amarilli, Antoine, et al.
Published: (2022)

Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions
by: Brown, Hera, et al.
Published: (2025)

Choiceless Computation and Symmetry: Limitations of Definability
by: Pago, Benedikt
Published: (2024)

Synthesizing nested relational queries from implicit specifications: via model theory and via proof theory
by: Benedikt, Michael, et al.
Published: (2022)

Vibe Coding an LLM-powered Theorem Prover
by: Hou, Zhe
Published: (2026)

Canonicity in power and modal logics of finite achronal width
by: Goldblatt, Robert, et al.
Published: (2022)

Decidability of Graph Neural Networks via Logical Characterizations
by: Benedikt, Michael, et al.
Published: (2024)

Parameterized Infinite-State Reactive Synthesis
by: Maderbacher, Benedikt, et al.
Published: (2025)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)

Optimal Lower Bounds for Symmetric Modular Circuits
by: Pago, Benedikt
Published: (2026)

Wider systems for linear logic with fixed points: proof theory and complexity
by: Das, Anupam, et al.
Published: (2026)

Gödel Incompleteness Theorem for PAC Learnable Theory from the view of complexity measurement
by: Ma, Zhifeng, et al.
Published: (2024)

LEGO-like Small-Model Constructions for Åqvist's Logics
by: Rozplokhas, Dmitry
Published: (2024)

Convergence Laws for Extensions of First-Order Logic with Averaging
by: Adam-Day, Sam, et al.
Published: (2025)

Two variable logic with ultimately periodic counting
by: Benedikt, Michael, et al.
Published: (2020)

Quasiminimality of complex powers
by: Gallinaro, Francesco, et al.
Published: (2023)