Logspace computations in Coxeter groups and graph groups.

DOI10.1090/CONM/582/11553MaRDI QIDQ2869260zbMATH OpenOpenAlexFDO

Authors Volker Diekert, Jonathan Kausch, Markus Lohrey

Publication date 3 January 2014

Published in Computational and Combinatorial Group Theory and Cryptography (Search for Journal in Brave)

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

zbMATH Keywords

deterministic Turing machinesfree partially commutative inverse monoidslengths of geodesic normal formsnormal form computationsnormal form theoremsright-angled Artin groupsright-angled Coxeter groupsword problem

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Braid groups; Artin groups (20F36) Reflection and Coxeter groups (group-theoretic aspects) (20F55) Geometric group theory (20F65) Free semigroups, generators and relations, word problems (20M05) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: Computing normal forms in groups (or monoids) is in general harder than solving the word problem (equality testing). However, normal form computation has a much wider range of applications. It is therefore interesting to investigate the complexity of computing normal forms for important classes of groups. For Coxeter groups we show that the following algorithmic tasks can be solved by a deterministic Turing machine using logarithmic work space, only: 1. Compute the length of any geodesic normal form. 2. Compute the set of letters occurring in any geodesic normal form. 3. Compute the Parikh-image of any geodesic normal form in case that all defining relations have even length (i.e., in even Coxeter groups.) 4. For right-angled Coxeter groups we can do actually compute the short length normal form in logspace. (Note that short length normal forms are geodesic.) Next, we apply the results to right-angled Artin groups. They are also known as free partially commutative groups or as graph groups. As a consequence of our result on right-angled Coxeter groups we show that shortlex normal forms in graph groups can be computed in logspace, too. Graph groups play an important role in group theory, and they have a close connection to concurrency theory. As an application of our results we show that the word problem for free partially commutative inverse monoids is in logspace. This result generalizes a result of Ondrusch and the third author on free inverse monoids. Concurrent systems which are deterministic and co-deterministic can be studied via inverse monoids.

Recommendations

• Logspace computations in graph groups and Coxeter groups.
• Logspace computations in graph products
• Logspace computations in graph products
• On groups that have normal forms computable in logspace.
• Logspace and compressed-word computations in nilpotent groups

Cited in

(9)

• Algorithms detecting stability and Morseness for finitely generated groups
• The power word problem in graph products
• Logspace computations in graph groups and Coxeter groups.
• Normal forms for automorphisms of universal Coxeter groups and palindromic automorphisms of free groups.
• On groups that have normal forms computable in logspace.
• Log-space conjugacy problem in the Grigorchuk group
• Logspace computations in graph products
• Logspace computations in graph products
• Groups with identities

This page was built for publication: Logspace computations in Coxeter groups and graph groups.

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