Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests

Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests

We study the computational complexity of existential Presburger arithmetic with (possibly nested occurrences of) a Kleene-star operator. In addition to being a natural extension of Presburger arithmetic, our investigation is motivated by two other decision problems. The first problem is the rational...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Haase, C, Zetzsche, G
Fformat:	Conference item
Cyhoeddwyd:	IEEE 2019

Eitemau Tebyg

Quantifier elimination for counting extensions of Presburger arithmetic
gan: Chistikov, D, et al.
Cyhoeddwyd: (2022)

Super-exponential Complexity of Presburger Arithmetic
gan: Fischer, Michael J., et al.
Cyhoeddwyd: (2023)

On the decidability of Presburger arithmetic expanded with powers
gan: Karimov, T, et al.
Cyhoeddwyd: (2025)

The complexity of Presburger arithmetic with power or powers
gan: Benedikt, M, et al.
Cyhoeddwyd: (2023)

Presburger Arithmetic with algebraic scalar multiplications
gan: Philipp Hieronymi, et al.
Cyhoeddwyd: (2021-07-01)

Abstraction−based Satisfiability Solving of Presburger Arithmetic
gan: Kroening, D, et al.
Cyhoeddwyd: (2004)

An Algorithm for Deciding BAPA: Boolean Algebra with Presburger Arithmetic
gan: Kuncak, Viktor, et al.
Cyhoeddwyd: (2005)

An interpolating sequent calculus for quantifier-free Presburger arithmetic
gan: Brillout, A, et al.
Cyhoeddwyd: (2011)

Beyond quantifier-free interpolation in extensions of presburger arithmetic
gan: Brillout, A, et al.
Cyhoeddwyd: (2011)

An Interpolating Sequent Calculus for Quantifier-Free Presburger Arithmetic.
gan: Brillout, A, et al.
Cyhoeddwyd: (2011)

On Presburger arithmetic extended with non-unary counting quantifiers
gan: Peter Habermehl, et al.
Cyhoeddwyd: (2023-07-01)

Unification modulo presburger arithmetic and other decidable theories
gan: Mauricio Ayala Rincón, et al.
Cyhoeddwyd: (2001-12-01)

Quantifier-Free Boolean Algebra with Presburger Arithmetic is NP-Complete
gan: Kuncak, Viktor
Cyhoeddwyd: (2007)

Extensions of Presburger arithmetic and model checking one-counter automata
gan: Lechner, A
Cyhoeddwyd: (2016)

Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
gan: Tristram Bogart, et al.
Cyhoeddwyd: (2017-01-01)

Quadratic Word Equations with Length Constraints, Counter Systems, and Presburger Arithmetic with Divisibility
gan: Anthony W. Lin, et al.
Cyhoeddwyd: (2021-10-01)

Enrichments of Boolean algebras by Presburger predicates
gan: Derakhshan, J, et al.
Cyhoeddwyd: (2017)

Rational subsets of finite groups
gan: Roger Alperin
Cyhoeddwyd: (2014-06-01)

Model theory of finite-by-Presburger Abelian groups and finite extensions of $p$-adic fields
gan: Derakhshan, J, et al.
Cyhoeddwyd: (2016)

Deciding whether the ordering is necessary in a Presburger formula
gan: Christian Choffrut, et al.
Cyhoeddwyd: (2010-01-01)

Decomposition of zero divisor graph into cycles and stars
gan: A.Kuppan, et al.
Cyhoeddwyd: (2023-01-01)

Automorphism groups of graph covers and uniform subset graphs
gan: N.B. Mumba, et al.
Cyhoeddwyd: (2018-04-01)

Automorphism groups of graph covers and uniform subset graphs
gan: N.B. Mumba, et al.
Cyhoeddwyd: (2018-04-01)

On two-variable guarded fragment logic with expressive local Presburger constraints
gan: Chia-Hsuan Lu, et al.
Cyhoeddwyd: (2024-08-01)

The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
gan: leroux jerome
Cyhoeddwyd: (2010-09-01)

Deciding Quantifier-Free Presburger Formulas Using Parameterized Solution Bounds
gan: Sanjit A. Seshia, et al.
Cyhoeddwyd: (2005-12-01)

Rational Arithmetic For Mini-Computers
gan: Horn, Berthold K.P.
Cyhoeddwyd: (2008)

Properties of rational arithmetic functions
gan: Vichian Laohakosol, et al.
Cyhoeddwyd: (2005-01-01)

Birational geometry, rational curves, and arithmetic /
gan: Bogomolov, Fedor, 1946-, editor, et al.
Cyhoeddwyd: (c201)

Simple Equational Specifications of Rational Arithmetic
gan: Lawrence S. Moss
Cyhoeddwyd: (2001-01-01)

Simple Equational Specifications of Rational Arithmetic
gan: Lawrence S. Moss
Cyhoeddwyd: (2001-12-01)

Star compressed zero divisors graph and partitions of vector spaces
gan: Hamid Reza Dorbidi
Cyhoeddwyd: (2023-10-01)

On the expressiveness of Büchi arithmetic
gan: Haase, C, et al.
Cyhoeddwyd: (2021)

On arithmetic–geometric eigenvalues of graphs
gan: Rather Bilal A., et al.
Cyhoeddwyd: (2022-08-01)

Siegel zeros and the least prime in an arithmetic progression
gan: Heath-Brown, D
Cyhoeddwyd: (1990)

The GHZ/W−calculus contains rational arithmetic
gan: Coecke, B, et al.
Cyhoeddwyd: (2011)

The GHZ/W−calculus contains rational arithmetic
gan: Coecke, B, et al.
Cyhoeddwyd: (2010)

Obstructions to arithmetic properties of rational points on varieties
gan: Balestrieri, F
Cyhoeddwyd: (2017)

The GHZ/W-calculus contains rational arithmetic
gan: Bob Coecke, et al.
Cyhoeddwyd: (2011-03-01)

Symmetries and symmetry-breaking in arithmetic graphs
gan: Aqsa Shah, et al.
Cyhoeddwyd: (2023-09-01)