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 groupsgraph productsconjugacy problemright-angled Artin groupsright-angled Coxeter groupsalgorithms for compressed stringscompressed word problemdecision problems for groups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Braid groups; Artin groups (20F36) Reflection and Coxeter groups (group-theoretic aspects) (20F55) Automorphism groups of groups (20F28) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (7)

Taming the hydra: The word problem and extreme integer compression ⋮ The power word problem in graph products ⋮ Logspace and compressed-word computations in nilpotent groups ⋮ Closure properties of knapsack semilinear groups ⋮ Unnamed Item ⋮ Logspace computations in graph products ⋮ Compression techniques in group theory

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

This page was built for publication: COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS