Reducibilities Among Decision Problems for HNN Groups, Vector Addition Systems and Subsystems of Peano Arithmetic

DOI10.2307/2045489zbMath0523.20025OpenAlexW4240215465MaRDI QIDQ3035687

Michael Anshel, Kenneth McAloon

Publication date: 1983

Full work available at URL: https://doi.org/10.2307/2045489

zbMATH Keywords

decision problemsPeano arithmeticAckermann functionvector groupsHNN groupspositive conjugate powersprimitive recursively decidablereachability sets in vector addition systemsspecial equality problem

Mathematics Subject Classification ID

Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Related Items (3)

A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ The Conjugacy Problem for HNN Extensions with Infinite Cyclic Associated Groups ⋮ On the finite containment problem for Petri nets

Cites Work

• Petri nets and large finite sets
• Proof theory. 2nd ed
• The equality problem for vector addition systems is undecidable
• The covering and boundedness problems for vector addition systems
• Parallel program schemata
• Vector Groups and the Equality Problem for Vector Addition Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reducibilities Among Decision Problems for HNN Groups, Vector Addition Systems and Subsystems of Peano Arithmetic