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

DOI10.2307/2045489zbMath0523.20025MaRDI QIDQ3035687

Kenneth McAloon, Michael Anshel

Publication date: 1983

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

zbMATH Keywords

decision problems; Peano arithmetic; Ackermann function; vector groups; HNN groups; positive conjugate powers; primitive recursively decidable; reachability sets in vector addition systems; special equality problem

Mathematics Subject Classification ID

20E06: Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

03D40: Word problems, etc. in computability and recursion theory

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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