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

Popoln opis

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