Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests

DOI10.5555/3470152.3470210MaRDI QIDQ6654523zbMATH OpenFDO

Authors Christoph Haase, Georg Zetzsche

Publication date 19 December 2024

Full work available at URL https://doi.org/10.5555/3470152.3470210

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The submonoid and rational subset membership problems for graph groups.
• On the rational subset problem for groups.
• The rational subset membership problem for groups: a survey
• Existential and positive theories of equations in graph products
• scientific article; zbMATH DE number 2086411

Cited in

(6)

• An efficient quantifier elimination procedure for Presburger arithmetic
• Flattability of priority vector addition systems
• Decidability of graph neural networks via logical characterizations
• New support size bounds for integer programming, applied to makespan minimization on uniformly related machines
• Membership problems in infinite groups
• An introduction to the theory of linear integer arithmetic (invited paper)

This page was built for publication: Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6654523)