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

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính:	Haase, C, Zetzsche, G
Định dạng:	Conference item
Được phát hành:	IEEE 2019

Những quyển sách tương tự

Quantifier elimination for counting extensions of Presburger arithmetic
Bằng: Chistikov, D, et al.
Được phát hành: (2022)

Super-exponential Complexity of Presburger Arithmetic
Bằng: Fischer, Michael J., et al.
Được phát hành: (2023)

On the decidability of Presburger arithmetic expanded with powers
Bằng: Karimov, T, et al.
Được phát hành: (2025)

The complexity of Presburger arithmetic with power or powers
Bằng: Benedikt, M, et al.
Được phát hành: (2023)

Presburger Arithmetic with algebraic scalar multiplications
Bằng: Philipp Hieronymi, et al.
Được phát hành: (2021-07-01)

Abstraction−based Satisfiability Solving of Presburger Arithmetic
Bằng: Kroening, D, et al.
Được phát hành: (2004)

An Algorithm for Deciding BAPA: Boolean Algebra with Presburger Arithmetic
Bằng: Kuncak, Viktor, et al.
Được phát hành: (2005)

An interpolating sequent calculus for quantifier-free Presburger arithmetic
Bằng: Brillout, A, et al.
Được phát hành: (2011)

Beyond quantifier-free interpolation in extensions of presburger arithmetic
Bằng: Brillout, A, et al.
Được phát hành: (2011)

An Interpolating Sequent Calculus for Quantifier-Free Presburger Arithmetic.
Bằng: Brillout, A, et al.
Được phát hành: (2011)

On Presburger arithmetic extended with non-unary counting quantifiers
Bằng: Peter Habermehl, et al.
Được phát hành: (2023-07-01)

Unification modulo presburger arithmetic and other decidable theories
Bằng: Mauricio Ayala Rincón, et al.
Được phát hành: (2001-12-01)

Quantifier-Free Boolean Algebra with Presburger Arithmetic is NP-Complete
Bằng: Kuncak, Viktor
Được phát hành: (2007)

Extensions of Presburger arithmetic and model checking one-counter automata
Bằng: Lechner, A
Được phát hành: (2016)

Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
Bằng: Tristram Bogart, et al.
Được phát hành: (2017-01-01)

Quadratic Word Equations with Length Constraints, Counter Systems, and Presburger Arithmetic with Divisibility
Bằng: Anthony W. Lin, et al.
Được phát hành: (2021-10-01)

Enrichments of Boolean algebras by Presburger predicates
Bằng: Derakhshan, J, et al.
Được phát hành: (2017)

Rational subsets of finite groups
Bằng: Roger Alperin
Được phát hành: (2014-06-01)

Model theory of finite-by-Presburger Abelian groups and finite extensions of $p$-adic fields
Bằng: Derakhshan, J, et al.
Được phát hành: (2016)

Deciding whether the ordering is necessary in a Presburger formula
Bằng: Christian Choffrut, et al.
Được phát hành: (2010-01-01)

Decomposition of zero divisor graph into cycles and stars
Bằng: A.Kuppan, et al.
Được phát hành: (2023-01-01)

Automorphism groups of graph covers and uniform subset graphs
Bằng: N.B. Mumba, et al.
Được phát hành: (2018-04-01)

Automorphism groups of graph covers and uniform subset graphs
Bằng: N.B. Mumba, et al.
Được phát hành: (2018-04-01)

On two-variable guarded fragment logic with expressive local Presburger constraints
Bằng: Chia-Hsuan Lu, et al.
Được phát hành: (2024-08-01)

The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
Bằng: leroux jerome
Được phát hành: (2010-09-01)

Deciding Quantifier-Free Presburger Formulas Using Parameterized Solution Bounds
Bằng: Sanjit A. Seshia, et al.
Được phát hành: (2005-12-01)

Rational Arithmetic For Mini-Computers
Bằng: Horn, Berthold K.P.
Được phát hành: (2008)

Properties of rational arithmetic functions
Bằng: Vichian Laohakosol, et al.
Được phát hành: (2005-01-01)

Birational geometry, rational curves, and arithmetic /
Bằng: Bogomolov, Fedor, 1946-, editor, et al.
Được phát hành: (c201)

Simple Equational Specifications of Rational Arithmetic
Bằng: Lawrence S. Moss
Được phát hành: (2001-01-01)

Simple Equational Specifications of Rational Arithmetic
Bằng: Lawrence S. Moss
Được phát hành: (2001-12-01)

Star compressed zero divisors graph and partitions of vector spaces
Bằng: Hamid Reza Dorbidi
Được phát hành: (2023-10-01)

On the expressiveness of Büchi arithmetic
Bằng: Haase, C, et al.
Được phát hành: (2021)

On arithmetic–geometric eigenvalues of graphs
Bằng: Rather Bilal A., et al.
Được phát hành: (2022-08-01)

Siegel zeros and the least prime in an arithmetic progression
Bằng: Heath-Brown, D
Được phát hành: (1990)

The GHZ/W−calculus contains rational arithmetic
Bằng: Coecke, B, et al.
Được phát hành: (2011)

The GHZ/W−calculus contains rational arithmetic
Bằng: Coecke, B, et al.
Được phát hành: (2010)

Obstructions to arithmetic properties of rational points on varieties
Bằng: Balestrieri, F
Được phát hành: (2017)

The GHZ/W-calculus contains rational arithmetic
Bằng: Bob Coecke, et al.
Được phát hành: (2011-03-01)

Symmetries and symmetry-breaking in arithmetic graphs
Bằng: Aqsa Shah, et al.
Được phát hành: (2023-09-01)