Polynomial-time word problems | Zendy

Saul Schleimer | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Polynomial-time word problems

Author(s) -

Saul Schleimer

Publication year - 2008

Publication title -

commentarii mathematici helvetici

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.603

H-Index - 46

eISSN - 1420-8946

pISSN - 0010-2571

DOI - 10.4171/cmh/142

Subject(s) - mathematics , word (group theory) , polynomial , word problem (mathematics education) , time complexity , arithmetic , algebra over a field , pure mathematics , combinatorics , geometry , mathematical analysis

We find polynomial-time solutions to the word problem for free-by-cyclic groups, the word problem for automorphism groups of free groups, and the membership problem for the handlebody subgroup of the mapping class group. All of these results follow from observing that automorphisms of the free group strongly resemble straight-line programs, which are widely studied in the theory of compressed data structures. In an effort to be self-contained we give a detailed exposition of the necessary results from computer science.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research