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

Journal of Algebra - Tập 345 - Trang 324 - 2011
Alexei Myasnikov1, Dong Wook Won2, Alexander Ushakov1
1Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ, USA
2Department of Mathematics, CUNY/LAGCC, Long Island City, NY, USA

Tóm tắt

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

Từ khóa

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

Tài liệu tham khảo

null null null null null null null null null null null null null null null null null null null null null null null null null null null null
Thông tin
Thông tin xuất bản

Journal of Algebra

Tập 345

324

Thông tin tác giả