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/

Global: Zendy Tools annual

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

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Power circuits are data structures which support efficient algorithms forhighly compressed integers. Using this new data structure it has been shownrecently by Myasnikov, Ushakov and Won that the Word Problem of the one-relatorBaumslag group is in P. Before that the best known upper bound has beennon-elementary. In the present paper we provide new results for power circuitsand we give new applications in algorithmic algebra and algorithmic grouptheory: 1. We define a modified reduction procedure on power circuits whichruns in quadratic time thereby improving the known cubic time complexity. Theimprovement is crucial for our other results. 2. We improve the complexity ofthe Word Problem for the Baumslag group to cubic time thereby providing thefirst practical algorithm for that problem. 3. The main result is that the WordProblem of Higman's group is decidable in polynomial time. The situation forHigman's group is more complicated than for the Baumslag group and forced us toadvance the theory of power circuits.

Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P