The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable

Alexei Myasnikov; Alexander Ushakov; Dong Wook Won

doi:10.1016/j.jalgebra.2011.07.024

The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable

Alexei Myasnikov, Alexander Ushakov, Dong Wook Won

Department of Mathematical Sciences

City University of New York

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

26 Scopus citations

Abstract

We prove that the Word Problem in the Baumslag group G_(1,2)=〈a,b;a^ab=a²〉 which has a non-elementary Dehn function is decidable in polynomial time.

Original language	English
Pages (from-to)	324-342
Number of pages	19
Journal	Journal of Algebra
Volume	345
Issue number	1
DOIs	https://doi.org/10.1016/j.jalgebra.2011.07.024
State	Published - 1 Nov 2011

Keywords

Baumslag group
Computational complexity
Magnus breakdown algorithm
One-relator group
Power circuit
Word Problem

Access to Document

10.1016/j.jalgebra.2011.07.024

Cite this

@article{0a4447546cc74e4eb37f4f2401fd734a,

title = "The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable",

abstract = "We prove that the Word Problem in the Baumslag group G(1,2)=〈a,b;aab=a2〉 which has a non-elementary Dehn function is decidable in polynomial time.",

keywords = "Baumslag group, Computational complexity, Magnus breakdown algorithm, One-relator group, Power circuit, Word Problem",

author = "Alexei Myasnikov and Alexander Ushakov and Won, {Dong Wook}",

year = "2011",

month = nov,

day = "1",

doi = "10.1016/j.jalgebra.2011.07.024",

language = "English",

volume = "345",

pages = "324--342",

number = "1",

}

TY - JOUR

T1 - The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable

AU - Myasnikov, Alexei

AU - Ushakov, Alexander

AU - Won, Dong Wook

PY - 2011/11/1

Y1 - 2011/11/1

N2 - We prove that the Word Problem in the Baumslag group G(1,2)=〈a,b;aab=a2〉 which has a non-elementary Dehn function is decidable in polynomial time.

AB - We prove that the Word Problem in the Baumslag group G(1,2)=〈a,b;aab=a2〉 which has a non-elementary Dehn function is decidable in polynomial time.

KW - Baumslag group

KW - Computational complexity

KW - Magnus breakdown algorithm

KW - One-relator group

KW - Power circuit

KW - Word Problem

UR - http://www.scopus.com/inward/record.url?scp=80052659106&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052659106&partnerID=8YFLogxK

U2 - 10.1016/j.jalgebra.2011.07.024

DO - 10.1016/j.jalgebra.2011.07.024

M3 - Article

AN - SCOPUS:80052659106

SN - 0021-8693

VL - 345

SP - 324

EP - 342

JO - Journal of Algebra

JF - Journal of Algebra

IS - 1

ER -

The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this