The Bounded and Precise Word Problems for Presentations of Groups

DOI10.1090/memo/1281OpenAlexW2473896820MaRDI QIDQ5113919

Sergei V. Ivanov

Publication date: 19 June 2020

Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

polygonal curvespresentations of groupsdiagramsword problemspolylogarithmic space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Cancellation theory of groups; application of van Kampen diagrams (20F06) Research exposition (monographs, survey articles) pertaining to group theory (20-02)

Cites Work

• Tangent unit-vector fields: nonabelian homotopy invariants and the Dirichlet energy
• On Dehn functions of infinite presentations of groups.
• Speeding up the dynamic algorithm for planar RNA folding
• Tangent unit-vector fields: non-abelian homotopy invariants and the Dirichlet energy
• On finding a minimum dominating set in a tournament
• Combinatorial group theory.
• On limited nondeterminism and the complexity of the V-C dimension
• Isoperimetric functions of groups and computational complexity of the word problem
• Relationships between nondeterministic and deterministic tape complexities
• The word problem in semi-groups with cancellation
• Word Problems Solvable in Logspace
• Algorithms for Loop Matchings
• THE FREE BURNSIDE GROUPS OF SUFFICIENTLY LARGE EXPONENTS
• Computing area in presentations of the trivial group
• Recursive Unsolvability of a problem of Thue
• Computational Complexity
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• The word problem
• On the complexity of some problems on groups input as multiplication tables
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Bounded and Precise Word Problems for Presentations of Groups