COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS

DOI10.1142/S0218196712400073zbMath1267.20050MaRDI QIDQ4904513

Markus Lohrey, Christian Mathissen, Niko Haubold

Publication date: 30 January 2013

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

zbMATH Keywords

outer automorphism groups; graph products; conjugacy problem; right-angled Artin groups; right-angled Coxeter groups; algorithms for compressed strings; compressed word problem; decision problems for groups

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

20F36: Braid groups; Artin groups

20F55: Reflection and Coxeter groups (group-theoretic aspects)

20F28: Automorphism groups of groups

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)

Related Items

Taming the hydra: The word problem and extreme integer compression, Logspace computations in graph products, Closure properties of knapsack semilinear groups

Cites Work

• Unnamed Item
• Unnamed Item
• Compressed word problems in HNN-extensions and amalgamated products
• Asynchronous mappings and asynchronous cellular automata
• Group-based cryptography
• Pattern matching and membership for hierarchical message sequence charts
• Polynomial-time word problems.
• Peak reduction and finite presentations for automorphism groups of right-angled Artin groups.
• The word problem for free partially commutative groups
• Combinatorics on traces
• Algorithms and geometry for graph products of groups
• Generic-case complexity, decision problems in group theory, and random walks.
• Isoperimetric inequalities for nilpotent groups.
• Automorphisms of graph groups.
• Automorphisms of 2-dimensional right-angled Artin groups.
• Efficient solution of some problems in free partially commutative monoids
• An introduction to right-angled Artin groups.
• A GENERATING SET FOR THE AUTOMORPHISM GROUP OF A GRAPH PRODUCT OF ABELIAN GROUPS
• On the algorithmic insolvability of the word problem in group theory
• WORD EQUATIONS OVER GRAPH PRODUCTS
• COMPRESSED WORDS AND AUTOMORPHISMS IN FULLY RESIDUALLY FREE GROUPS
• Finiteness properties of automorphism groups of right-angled Artin groups
• The conjugacy problem in subgroups of right-angled Artin groups
• Word Problems Solvable in Logspace
• A complex for right-angled Coxeter groups
• A Generating Set for the Automorphism Group of a Graph Group
• Word Problems and Membership Problems on Compressed Words
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• The word problem