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

Baumslag-Solitar groups were introduced in 1962 by Baumslag and Solitar asexamples for finitely presented non-Hopfian two-generator groups. Since then,they served as examples for a wide range of purposes. As Baumslag-Solitargroups are HNN extensions, there is a natural generalization in terms of graphof groups.  Concerning algorithmic aspects of generalized Baumslag-Solitar groups,several decidability results are known. Indeed, a straightforward applicationof standard algorithms leads to a polynomial time solution of the word problem(the question whether some word over the generators represents the identity ofthe group). The conjugacy problem (the question whether two given wordsrepresent conjugate group elements) is more complicated; still decidability hasbeen established by Anshel and Stebe for ordinary Baumslag-Solitar groups andfor generalized Baumslag-Solitar groups independently by Lockhart and Beeker.However, up to now no precise complexity estimates have been given.  In this work, we give a LOGSPACE algorithm for both problems. More precisely,we describe a uniform TC^0 many-one reduction of the word problem to the wordproblem of the free group. Then we refine the known techniques for theconjugacy problem and show that it can be solved in LOGSPACE. Moreover, forordinary Baumslag-Solitar groups also conjugacy is AC^0-Turing-reducible to theword problem of the free group.  Finally, we consider uniform versions (where also the graph of groups is partof the input) of both word and conjugacy problem: while the word problem stillis solvable in LOGSPACE, the conjugacy problem becomes EXPSPACE-complete.

A Logspace Solution to the Word and Conjugacy problem of Generalized Baumslag-Solitar Groups