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

Bibliografske podrobnosti
Main Authors:	Haase, C, Zetzsche, G
Format:	Conference item
Izdano:	IEEE 2019

Podobne knjige/članki

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Rational subsets of finite groups
od: Roger Alperin
Izdano: (2014-06-01)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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