Algorithmically complex residually finite groups

Olga Kharlampovich; Alexei Myasnikov; Mark Sapir

doi:10.1007/s13373-017-0103-z

Algorithmically complex residually finite groups

Olga Kharlampovich
, Alexei Myasnikov
, Mark Sapir

Department of Mathematical Sciences

City University of New York
Vanderbilt University

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

Abstract

We construct the first examples of algorithmically complex finitely presented residually finite groups and the first examples of finitely presented residually finite groups with arbitrarily large (recursive) Dehn functions, and arbitrarily large depth functions. The groups are solvable of class 3.

Original language	English
Pages (from-to)	309-352
Number of pages	44
Journal	Bulletin of Mathematical Sciences
Volume	7
Issue number	2
DOIs	https://doi.org/10.1007/s13373-017-0103-z
State	Published - 1 Aug 2017

Keywords

Dehn function
Depth function
Minsky machine
Word problem

Access to Document

10.1007/s13373-017-0103-z

Cite this

@article{8e5ea224aa1640b2bc9a415e25cd4d86,

title = "Algorithmically complex residually finite groups",

abstract = "We construct the first examples of algorithmically complex finitely presented residually finite groups and the first examples of finitely presented residually finite groups with arbitrarily large (recursive) Dehn functions, and arbitrarily large depth functions. The groups are solvable of class 3.",

keywords = "Dehn function, Depth function, Minsky machine, Word problem",

author = "Olga Kharlampovich and Alexei Myasnikov and Mark Sapir",

note = "Publisher Copyright: {\textcopyright} 2017, The Author(s).",

year = "2017",

month = aug,

day = "1",

doi = "10.1007/s13373-017-0103-z",

language = "English",

volume = "7",

pages = "309--352",

number = "2",

}

TY - JOUR

T1 - Algorithmically complex residually finite groups

AU - Kharlampovich, Olga

AU - Myasnikov, Alexei

AU - Sapir, Mark

PY - 2017/8/1

Y1 - 2017/8/1

N2 - We construct the first examples of algorithmically complex finitely presented residually finite groups and the first examples of finitely presented residually finite groups with arbitrarily large (recursive) Dehn functions, and arbitrarily large depth functions. The groups are solvable of class 3.

AB - We construct the first examples of algorithmically complex finitely presented residually finite groups and the first examples of finitely presented residually finite groups with arbitrarily large (recursive) Dehn functions, and arbitrarily large depth functions. The groups are solvable of class 3.

KW - Dehn function

KW - Depth function

KW - Minsky machine

KW - Word problem

UR - https://www.scopus.com/pages/publications/85024378829

UR - https://www.scopus.com/pages/publications/85024378829#tab=citedBy

U2 - 10.1007/s13373-017-0103-z

DO - 10.1007/s13373-017-0103-z

M3 - Article

AN - SCOPUS:85024378829

SN - 1664-3607

VL - 7

SP - 309

EP - 352

JO - Bulletin of Mathematical Sciences

JF - Bulletin of Mathematical Sciences

IS - 2

ER -

Algorithmically complex residually finite groups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this