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

书目详细资料
Main Authors:	Haase, C, Zetzsche, G
格式:	Conference item
出版:	IEEE 2019

相似书籍

Quantifier elimination for counting extensions of Presburger arithmetic
由: Chistikov, D, et al.
出版: (2022)

Super-exponential Complexity of Presburger Arithmetic
由: Fischer, Michael J., et al.
出版: (2023)

On the decidability of Presburger arithmetic expanded with powers
由: Karimov, T, et al.
出版: (2025)

The complexity of Presburger arithmetic with power or powers
由: Benedikt, M, et al.
出版: (2023)

Presburger Arithmetic with algebraic scalar multiplications
由: Philipp Hieronymi, et al.
出版: (2021-07-01)

Abstraction−based Satisfiability Solving of Presburger Arithmetic
由: Kroening, D, et al.
出版: (2004)

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

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

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

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

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

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

Quantifier-Free Boolean Algebra with Presburger Arithmetic is NP-Complete
由: Kuncak, Viktor
出版: (2007)

Extensions of Presburger arithmetic and model checking one-counter automata
由: Lechner, A
出版: (2016)

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

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

Enrichments of Boolean algebras by Presburger predicates
由: Derakhshan, J, et al.
出版: (2017)

Rational subsets of finite groups
由: Roger Alperin
出版: (2014-06-01)

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

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

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

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

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

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

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

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

Rational Arithmetic For Mini-Computers
由: Horn, Berthold K.P.
出版: (2008)

Properties of rational arithmetic functions
由: Vichian Laohakosol, et al.
出版: (2005-01-01)

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

Simple Equational Specifications of Rational Arithmetic
由: Lawrence S. Moss
出版: (2001-01-01)

Simple Equational Specifications of Rational Arithmetic
由: Lawrence S. Moss
出版: (2001-12-01)

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

On the expressiveness of Büchi arithmetic
由: Haase, C, et al.
出版: (2021)

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

Siegel zeros and the least prime in an arithmetic progression
由: Heath-Brown, D
出版: (1990)

The GHZ/W−calculus contains rational arithmetic
由: Coecke, B, et al.
出版: (2011)

The GHZ/W−calculus contains rational arithmetic
由: Coecke, B, et al.
出版: (2010)

Obstructions to arithmetic properties of rational points on varieties
由: Balestrieri, F
出版: (2017)

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

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