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...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Haase, C, Zetzsche, G
Formáid:	Conference item
Foilsithe / Cruthaithe:	IEEE 2019

Míreanna comhchosúla

Quantifier elimination for counting extensions of Presburger arithmetic
de réir: Chistikov, D, et al.
Foilsithe / Cruthaithe: (2022)

Super-exponential Complexity of Presburger Arithmetic
de réir: Fischer, Michael J., et al.
Foilsithe / Cruthaithe: (2023)

On the decidability of Presburger arithmetic expanded with powers
de réir: Karimov, T, et al.
Foilsithe / Cruthaithe: (2025)

The complexity of Presburger arithmetic with power or powers
de réir: Benedikt, M, et al.
Foilsithe / Cruthaithe: (2023)

Presburger Arithmetic with algebraic scalar multiplications
de réir: Philipp Hieronymi, et al.
Foilsithe / Cruthaithe: (2021-07-01)

Abstraction−based Satisfiability Solving of Presburger Arithmetic
de réir: Kroening, D, et al.
Foilsithe / Cruthaithe: (2004)

An Algorithm for Deciding BAPA: Boolean Algebra with Presburger Arithmetic
de réir: Kuncak, Viktor, et al.
Foilsithe / Cruthaithe: (2005)

An interpolating sequent calculus for quantifier-free Presburger arithmetic
de réir: Brillout, A, et al.
Foilsithe / Cruthaithe: (2011)

Beyond quantifier-free interpolation in extensions of presburger arithmetic
de réir: Brillout, A, et al.
Foilsithe / Cruthaithe: (2011)

An Interpolating Sequent Calculus for Quantifier-Free Presburger Arithmetic.
de réir: Brillout, A, et al.
Foilsithe / Cruthaithe: (2011)

On Presburger arithmetic extended with non-unary counting quantifiers
de réir: Peter Habermehl, et al.
Foilsithe / Cruthaithe: (2023-07-01)

Unification modulo presburger arithmetic and other decidable theories
de réir: Mauricio Ayala Rincón, et al.
Foilsithe / Cruthaithe: (2001-12-01)

Quantifier-Free Boolean Algebra with Presburger Arithmetic is NP-Complete
de réir: Kuncak, Viktor
Foilsithe / Cruthaithe: (2007)

Extensions of Presburger arithmetic and model checking one-counter automata
de réir: Lechner, A
Foilsithe / Cruthaithe: (2016)

Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
de réir: Tristram Bogart, et al.
Foilsithe / Cruthaithe: (2017-01-01)

Quadratic Word Equations with Length Constraints, Counter Systems, and Presburger Arithmetic with Divisibility
de réir: Anthony W. Lin, et al.
Foilsithe / Cruthaithe: (2021-10-01)

Enrichments of Boolean algebras by Presburger predicates
de réir: Derakhshan, J, et al.
Foilsithe / Cruthaithe: (2017)

Rational subsets of finite groups
de réir: Roger Alperin
Foilsithe / Cruthaithe: (2014-06-01)

Model theory of finite-by-Presburger Abelian groups and finite extensions of $p$-adic fields
de réir: Derakhshan, J, et al.
Foilsithe / Cruthaithe: (2016)

Deciding whether the ordering is necessary in a Presburger formula
de réir: Christian Choffrut, et al.
Foilsithe / Cruthaithe: (2010-01-01)

Decomposition of zero divisor graph into cycles and stars
de réir: A.Kuppan, et al.
Foilsithe / Cruthaithe: (2023-01-01)

Automorphism groups of graph covers and uniform subset graphs
de réir: N.B. Mumba, et al.
Foilsithe / Cruthaithe: (2018-04-01)

Automorphism groups of graph covers and uniform subset graphs
de réir: N.B. Mumba, et al.
Foilsithe / Cruthaithe: (2018-04-01)

On two-variable guarded fragment logic with expressive local Presburger constraints
de réir: Chia-Hsuan Lu, et al.
Foilsithe / Cruthaithe: (2024-08-01)

The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
de réir: leroux jerome
Foilsithe / Cruthaithe: (2010-09-01)

Deciding Quantifier-Free Presburger Formulas Using Parameterized Solution Bounds
de réir: Sanjit A. Seshia, et al.
Foilsithe / Cruthaithe: (2005-12-01)

Rational Arithmetic For Mini-Computers
de réir: Horn, Berthold K.P.
Foilsithe / Cruthaithe: (2008)

Properties of rational arithmetic functions
de réir: Vichian Laohakosol, et al.
Foilsithe / Cruthaithe: (2005-01-01)

Birational geometry, rational curves, and arithmetic /
de réir: Bogomolov, Fedor, 1946-, editor, et al.
Foilsithe / Cruthaithe: (c201)

Simple Equational Specifications of Rational Arithmetic
de réir: Lawrence S. Moss
Foilsithe / Cruthaithe: (2001-01-01)

Simple Equational Specifications of Rational Arithmetic
de réir: Lawrence S. Moss
Foilsithe / Cruthaithe: (2001-12-01)

Star compressed zero divisors graph and partitions of vector spaces
de réir: Hamid Reza Dorbidi
Foilsithe / Cruthaithe: (2023-10-01)

On the expressiveness of Büchi arithmetic
de réir: Haase, C, et al.
Foilsithe / Cruthaithe: (2021)

On arithmetic–geometric eigenvalues of graphs
de réir: Rather Bilal A., et al.
Foilsithe / Cruthaithe: (2022-08-01)

Siegel zeros and the least prime in an arithmetic progression
de réir: Heath-Brown, D
Foilsithe / Cruthaithe: (1990)

The GHZ/W−calculus contains rational arithmetic
de réir: Coecke, B, et al.
Foilsithe / Cruthaithe: (2011)

The GHZ/W−calculus contains rational arithmetic
de réir: Coecke, B, et al.
Foilsithe / Cruthaithe: (2010)

Obstructions to arithmetic properties of rational points on varieties
de réir: Balestrieri, F
Foilsithe / Cruthaithe: (2017)

The GHZ/W-calculus contains rational arithmetic
de réir: Bob Coecke, et al.
Foilsithe / Cruthaithe: (2011-03-01)

Symmetries and symmetry-breaking in arithmetic graphs
de réir: Aqsa Shah, et al.
Foilsithe / Cruthaithe: (2023-09-01)