SLP compression for solutions of equations with constraints in free and hyperbolic groups

DOI10.1142/S0218196715400056zbMath1328.20061arXiv1308.5586MaRDI QIDQ5246505

O. G. Kharlampovich, Atefeh Mohajeri Moghaddam, Volker Diekert

Publication date: 21 April 2015

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.5586

zbMATH Keywords

compressionNP-completenessstraight-line programscombinatorial group theorysystems of equationsrelatively hyperbolic groupsequations with constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algebraic geometry over groups; equations over groups (20F70)

Cites Work

• Maintaining dynamic sequences under equality tests in polylogarithmic time
• Polynomial-time word problems.
• The solvability problem for quadratic equations over free groups is NP-complete
• Canonical representatives and equations in hyperbolic groups
• Accidental parabolics and relatively hyperbolic groups.
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• Existential questions in (relatively) hyperbolic groups.
• Algorithmics on SLP-compressed strings: A survey
• Foliations for solving equations in groups: free, virtually free, and hyperbolic groups
• Recompression: Word Equations and Beyond
• Word Problems and Membership Problems on Compressed Words