Open Research Newcastle
Browse

On groups that have normal forms computable in logspace

Download (256.63 kB)
journal contribution
posted on 2025-05-11, 23:11 authored by Murray Elder, Gillian Elston, Gretchen Ostheimer
We consider the class of finitely generated groups which have a normal form computable in logspace. We prove that the class of such groups is closed under passing to finite index subgroups, direct products, wreath products, and certain free products and infinite extensions, and includes the solvable Baumslag–Solitar groups, as well as non-residually finite (and hence non-linear) examples. We define a group to be logspace embeddable if it embeds in a group with normal forms computable in logspace. We prove that finitely generated nilpotent groups are logspace embeddable. It follows that all groups of polynomial growth are logspace embeddable.

History

Journal title

Journal of Algebra

Volume

381

Issue

1

Pagination

260-281

Publisher

Elsevier

Language

  • en, English

College/Research Centre

Faculty of Science and Information Technology

School

School of Mathematical and Physical Sciences

Rights statement

© 2013. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/.

Usage metrics

    Publications

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC