English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Computing normal forms in groups (or monoids) is in general harder thansolving the word problem (equality testing). However, normal form computationhas a much wider range of applications. It is therefore interesting toinvestigate the complexity of computing normal forms for important classes ofgroups.  For Coxeter groups we show that the following algorithmic tasks can be solvedby a deterministic Turing machine using logarithmic work space, only: 1.Compute the length of any geodesic normal form. 2. Compute the set of lettersoccurring in any geodesic normal form. 3. Compute the Parikh-image of anygeodesic 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 doactually compute the short length normal form in logspace. (Note that shortlength normal forms are geodesic.)  Next, we apply the results to right-angled Artin groups. They are also knownas free partially commutative groups or as graph groups. As a consequence ofour result on right-angled Coxeter groups we show that shortlex normal forms ingraph groups can be computed in logspace, too. Graph groups play an importantrole 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 freepartially commutative inverse monoids is in logspace. This result generalizes aresult of Ondrusch and the third author on free inverse monoids. Concurrentsystems which are deterministic and co-deterministic can be studied via inversemonoids.

Logspace Computations in Coxeter Groups and Graph Groups