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

Fuld beskrivelse

Bibliografiske detaljer
Main Authors:	Haase, C, Zetzsche, G
Format:	Conference item
Udgivet:	IEEE 2019

Lignende værker

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Rational subsets of finite groups
af: Roger Alperin
Udgivet: (2014-06-01)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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