Logspace computations in graph products

DOI10.1145/2608628.2608642MaRDI QIDQ5899516zbMATH OpenOpenAlexFDO

Authors Volker Diekert, Jonathan Kausch

Publication date 11 November 2015

Published in Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic group theory

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph operations (line graphs, products, etc.) (05C76) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: We consider three important and well-studied algorithmic problems in group theory: the word, geodesic, and conjugacy problem. We show transfer results from individual groups to graph products. We concentrate on logspace complexity because the challenge is actually in small complexity classes, only. The most difficult transfer result is for the conjugacy problem. We have a general result for graph products, but even in the special case of a graph group the result is new. Graph groups are closely linked to the theory of Mazurkiewicz traces which form an algebraic model for concurrent processes. Our proofs are combinatorial and based on well-known concepts in trace theory. We also use rewriting techniques over traces. For the group-theoretical part we apply Bass-Serre theory. But as we need explicit formulae and as we design concrete algorithms all our group-theoretical calculations are completely explicit and accessible to non-specialists.

Recommendations

• Logspace computations in graph products
• Logspace computations in graph groups and Coxeter groups.
• Logspace computations in Coxeter groups and graph groups.
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups

Cites work

• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Cylindrical algebraic decomposition using validated numerics
• Definability and decision problems in arithmetic
• scientific article; zbMATH DE number 1952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• Jordan
• On Computable Numbers, with an Application to the Entscheidungsproblem
• The Jordan Curve Theorem, Formally and Informally

Cited in

(5)

• Logspace computations in Coxeter groups and graph groups.
• Logspace computations in graph groups and Coxeter groups.
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• scientific article; zbMATH DE number 4145340 (Why is no real title available?)
• Logspace computations in graph products

Describes a project that uses

Uses Software

• Jordan

This page was built for publication: Logspace computations in graph products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899516)