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

Полное описание

Библиографические подробности
Главные авторы:	Haase, C, Zetzsche, G
Формат:	Conference item
Опубликовано:	IEEE 2019

Схожие документы

Quantifier elimination for counting extensions of Presburger arithmetic
по: Chistikov, D, и др.
Опубликовано: (2022)

Super-exponential Complexity of Presburger Arithmetic
по: Fischer, Michael J., и др.
Опубликовано: (2023)

On the decidability of Presburger arithmetic expanded with powers
по: Karimov, T, и др.
Опубликовано: (2025)

The complexity of Presburger arithmetic with power or powers
по: Benedikt, M, и др.
Опубликовано: (2023)

Presburger Arithmetic with algebraic scalar multiplications
по: Philipp Hieronymi, и др.
Опубликовано: (2021-07-01)

Abstraction−based Satisfiability Solving of Presburger Arithmetic
по: Kroening, D, и др.
Опубликовано: (2004)

An Algorithm for Deciding BAPA: Boolean Algebra with Presburger Arithmetic
по: Kuncak, Viktor, и др.
Опубликовано: (2005)

An interpolating sequent calculus for quantifier-free Presburger arithmetic
по: Brillout, A, и др.
Опубликовано: (2011)

Beyond quantifier-free interpolation in extensions of presburger arithmetic
по: Brillout, A, и др.
Опубликовано: (2011)

An Interpolating Sequent Calculus for Quantifier-Free Presburger Arithmetic.
по: Brillout, A, и др.
Опубликовано: (2011)

On Presburger arithmetic extended with non-unary counting quantifiers
по: Peter Habermehl, и др.
Опубликовано: (2023-07-01)

Unification modulo presburger arithmetic and other decidable theories
по: Mauricio Ayala Rincón, и др.
Опубликовано: (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, и др.
Опубликовано: (2017-01-01)

Quadratic Word Equations with Length Constraints, Counter Systems, and Presburger Arithmetic with Divisibility
по: Anthony W. Lin, и др.
Опубликовано: (2021-10-01)

Enrichments of Boolean algebras by Presburger predicates
по: Derakhshan, J, и др.
Опубликовано: (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, и др.
Опубликовано: (2016)

Deciding whether the ordering is necessary in a Presburger formula
по: Christian Choffrut, и др.
Опубликовано: (2010-01-01)

Decomposition of zero divisor graph into cycles and stars
по: A.Kuppan, и др.
Опубликовано: (2023-01-01)

Automorphism groups of graph covers and uniform subset graphs
по: N.B. Mumba, и др.
Опубликовано: (2018-04-01)

Automorphism groups of graph covers and uniform subset graphs
по: N.B. Mumba, и др.
Опубликовано: (2018-04-01)

On two-variable guarded fragment logic with expressive local Presburger constraints
по: Chia-Hsuan Lu, и др.
Опубликовано: (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, и др.
Опубликовано: (2005-12-01)

Rational Arithmetic For Mini-Computers
по: Horn, Berthold K.P.
Опубликовано: (2008)

Properties of rational arithmetic functions
по: Vichian Laohakosol, и др.
Опубликовано: (2005-01-01)

Birational geometry, rational curves, and arithmetic /
по: Bogomolov, Fedor, 1946-, editor, и др.
Опубликовано: (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, и др.
Опубликовано: (2021)

On arithmetic–geometric eigenvalues of graphs
по: Rather Bilal A., и др.
Опубликовано: (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, и др.
Опубликовано: (2011)

The GHZ/W−calculus contains rational arithmetic
по: Coecke, B, и др.
Опубликовано: (2010)

Obstructions to arithmetic properties of rational points on varieties
по: Balestrieri, F
Опубликовано: (2017)

The GHZ/W-calculus contains rational arithmetic
по: Bob Coecke, и др.
Опубликовано: (2011-03-01)

Symmetries and symmetry-breaking in arithmetic graphs
по: Aqsa Shah, и др.
Опубликовано: (2023-09-01)