On parameterized complexity of the word search problem in the Baumslag-Gersten group

Alexei Miasnikov; Andrey Nikolaev

doi:10.1145/3373207.3404042

On parameterized complexity of the word search problem in the Baumslag-Gersten group

Alexei Miasnikov, Andrey Nikolaev

Department of Mathematical Sciences

Stevens Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We consider the word search problem in the Baumslag-Gersten group GB. We show that the parameterized complexity of this problem, where the area of van Kampen diagram serves as a parameter, is polynomial in the length of the input and the parameter. This contrasts the well-known result that the Dehn function and the time complexity of the word search problem in GB are non-elementary.

Original language	English
Title of host publication	ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation
Editors	Angelos Mantzaflaris
Publisher	Association for Computing Machinery
Pages	360-363
Number of pages	4
ISBN (Electronic)	9781450371001
DOIs	https://doi.org/10.1145/3373207.3404042
State	Published - Jul 20 2020
Event	45th International Symposium on Symbolic and Algebraic Computation, ISSAC 2020 - Kalamata, Virtual, Greece Duration: Jul 20 2020 → Jul 23 2020

Publication series

Name	Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Conference

Conference	45th International Symposium on Symbolic and Algebraic Computation, ISSAC 2020
Country/Territory	Greece
City	Kalamata, Virtual
Period	7/20/20 → 7/23/20

ASJC Scopus subject areas

General Mathematics

Keywords

Baumslag-Gersten group
Baumslag-Solitar group
dehn function
fixed parameter tractability
parameterized complexity
word problem
word search problem

Access to Document

10.1145/3373207.3404042

Cite this

Miasnikov, A., & Nikolaev, A. (2020). On parameterized complexity of the word search problem in the Baumslag-Gersten group. In A. Mantzaflaris (Ed.), ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (pp. 360-363). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). Association for Computing Machinery. https://doi.org/10.1145/3373207.3404042

Miasnikov, Alexei ; Nikolaev, Andrey. / On parameterized complexity of the word search problem in the Baumslag-Gersten group. ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation. editor / Angelos Mantzaflaris. Association for Computing Machinery, 2020. pp. 360-363 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

@inproceedings{3c8fb222bfa94732bb995079a4fa5950,

title = "On parameterized complexity of the word search problem in the Baumslag-Gersten group",

abstract = "We consider the word search problem in the Baumslag-Gersten group GB. We show that the parameterized complexity of this problem, where the area of van Kampen diagram serves as a parameter, is polynomial in the length of the input and the parameter. This contrasts the well-known result that the Dehn function and the time complexity of the word search problem in GB are non-elementary.",

keywords = "Baumslag-Gersten group, Baumslag-Solitar group, dehn function, fixed parameter tractability, parameterized complexity, word problem, word search problem",

author = "Alexei Miasnikov and Andrey Nikolaev",

note = "Publisher Copyright: {\textcopyright} 2020 ACM.; 45th International Symposium on Symbolic and Algebraic Computation, ISSAC 2020 ; Conference date: 20-07-2020 Through 23-07-2020",

year = "2020",

month = jul,

day = "20",

doi = "10.1145/3373207.3404042",

language = "English",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

publisher = "Association for Computing Machinery",

pages = "360--363",

editor = "Angelos Mantzaflaris",

booktitle = "ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation",

}

Miasnikov, A & Nikolaev, A 2020, On parameterized complexity of the word search problem in the Baumslag-Gersten group. in A Mantzaflaris (ed.), ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, Association for Computing Machinery, pp. 360-363, 45th International Symposium on Symbolic and Algebraic Computation, ISSAC 2020, Kalamata, Virtual, Greece, 7/20/20. https://doi.org/10.1145/3373207.3404042

On parameterized complexity of the word search problem in the Baumslag-Gersten group. / Miasnikov, Alexei ; Nikolaev, Andrey.
ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation. ed. / Angelos Mantzaflaris. Association for Computing Machinery, 2020. p. 360-363 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On parameterized complexity of the word search problem in the Baumslag-Gersten group

AU - Miasnikov, Alexei

AU - Nikolaev, Andrey

PY - 2020/7/20

Y1 - 2020/7/20

N2 - We consider the word search problem in the Baumslag-Gersten group GB. We show that the parameterized complexity of this problem, where the area of van Kampen diagram serves as a parameter, is polynomial in the length of the input and the parameter. This contrasts the well-known result that the Dehn function and the time complexity of the word search problem in GB are non-elementary.

AB - We consider the word search problem in the Baumslag-Gersten group GB. We show that the parameterized complexity of this problem, where the area of van Kampen diagram serves as a parameter, is polynomial in the length of the input and the parameter. This contrasts the well-known result that the Dehn function and the time complexity of the word search problem in GB are non-elementary.

KW - Baumslag-Gersten group

KW - Baumslag-Solitar group

KW - dehn function

KW - fixed parameter tractability

KW - parameterized complexity

KW - word problem

KW - word search problem

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

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

U2 - 10.1145/3373207.3404042

DO - 10.1145/3373207.3404042

M3 - Conference contribution

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 360

EP - 363

BT - ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation

A2 - Mantzaflaris, Angelos

PB - Association for Computing Machinery

T2 - 45th International Symposium on Symbolic and Algebraic Computation, ISSAC 2020

Y2 - 20 July 2020 through 23 July 2020

ER -

Miasnikov A , Nikolaev A. On parameterized complexity of the word search problem in the Baumslag-Gersten group. In Mantzaflaris A, editor, ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation. Association for Computing Machinery. 2020. p. 360-363. (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). doi: 10.1145/3373207.3404042

On parameterized complexity of the word search problem in the Baumslag-Gersten group

Abstract

Publication series

Conference

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this