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

Descripció completa

Dades bibliogràfiques
Autors principals:	Haase, C, Zetzsche, G
Format:	Conference item
Publicat:	IEEE 2019

Ítems similars

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Rational subsets of finite groups
per: Roger Alperin
Publicat: (2014-06-01)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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