The isomorphism problem for finite extensions of free groups is in PSPACE
From MaRDI portal
Publication:5002826
DOI10.4230/LIPIcs.ICALP.2018.139zbMath1499.20085arXiv1802.07085MaRDI QIDQ5002826
Géraud Sénizergues, Armin Weiß
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1802.07085
Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
On groups presented by inverse-closed finite confluent length-reducing rewriting systems ⋮ Solutions to twisted word equations and equations in virtually free groups
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The isomorphism problem for all hyperbolic groups.
- Groups, the theory of ends, and context-free languages
- The theory of ends, pushdown automata, and second-order logic
- Actions of finite groups of graphs and related automorphisms of free groups
- Vertex-transitive graphs and accessibility
- A taxonomy of complexity classes of functions
- Deformation and rigidity of simplicial group actions on trees.
- Deformation spaces of trees.
- Algorithmic and geometric topics around free groups and automorphisms. Based on the summer school, Barcelona, Spain, September--December 2012
- On Cayley graphs of virtually free groups
- Whitehead moves for G -trees
- Finite and infinite cyclic extensions of free groups
- An effective version of Stallings' theorem in the case of context-free groups
- CONTEXT-FREE GROUPS AND THEIR STRUCTURE TREES
- The word problem
This page was built for publication: The isomorphism problem for finite extensions of free groups is in PSPACE
