A new algorithm for solving the word problem in braid groups (Q1604340): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: David Garber / rank | |||
Property / author | |||
Property / author: Shmuel Kaplan / rank | |||
Property / reviewed by | |||
Property / reviewed by: Oleg V. Belegradek / rank | |||
Property / author | |||
Property / author: David Garber / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Shmuel Kaplan / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Oleg V. Belegradek / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2053986282 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0101053 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Theory of braids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new approach to the word and conjugacy problems in the braid groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Braid Groups and Left Distributive Operations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: FROM LARGE CARDINALS TO BRAIDS VIA DISTRIBUTIVE ALGEBRA / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A fast method for comparing braids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ALGORITHMS FOR POSITIVE BRAIDS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4949387 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: THE BRAID GROUP AND OTHER GROUPS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On complexity of the word problem in braid groups and mapping class groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: About the effective classification of conjugacy classes of braids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Band-generator presentation for the 4-braid group / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3828120 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:29, 4 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new algorithm for solving the word problem in braid groups |
scientific article |
Statements
A new algorithm for solving the word problem in braid groups (English)
0 references
4 July 2002
0 references
Artin's braid group \(B_n\) is the group presented in generators \(\sigma_1,\dots,\sigma_{n-1}\) by the defining relations \(\sigma_i\sigma_j=\sigma_j\sigma_i\) for \(i+1<j\), and \(\sigma_i\sigma_{i+1}\sigma_i=\sigma_{i+1}\sigma_i\sigma_{i+1}\) for \(i<n-1\). The word problem in \(B_n\) is solvable; the first algorithm was given by \textit{F.~A. Garside} [Q. J. Math., Oxf. II. Ser. 20, 235-254 (1969; Zbl 0194.03303)]. Since then many other algorithms were found; they were based on a suitable choice of generators in \(B_n\) and transforming a given braid to a certain normal form in those generators. The fastest known algorithm is of complexity \(O(nl^2)\), where \(l\) is the length of the braid word. The authors suggest a new algorithm for solving the word problem in \(B_n\) based on the topological definition of \(B_n\), due to \textit{B.~Moishezon} and \textit{M.~Teicher} [Contemp.~Math. 78, 425-455 (1988; Zbl 0674.14019)]. Let \(D\) be a closed disk, \(K\) a set of \(n\) points inside \(D\), and \(u\in\partial D\). The fundamental group \(G=\pi_1(D\setminus K,u)\) is known to be a free group with \(n\) generators. Any diffeomorphism of \(D\), which is the identity on \(\partial G\) and setwise fixes \(K\), induces an automorphism of \(G\), and the group \(\mathcal B\) of all such diffeomorphisms acts on \(G\) by automorphisms. Let \(B_n[D,K]\) be the group \(\mathcal B\) modulo the kernel of the action. Moishezon and Teicher proved that \(B_n[D,K]\simeq B_n\), constructing \(n-1\) generators in \(B_n[D,K]\) which witness the isomorphism. The free bases of \(G\), which arise from the \(n\)-tuples of loops of a certain type, play a special role and are called geometric bases. The group \(B_n(D,K)\) regularly acts on the geometric bases of \(G\). In order to determine whether two words are equal in \(B_n[D,K]\), one needs to check whether their actions on the elements of a chosen geometric basis are identical. To make the checking procedure efficient, the authors produce a computerized presentation of geometric bases, and two algorithms: for computing the action, and for reducing a presentation into a unique form. This gives a solution of the word problem in the braid group. The authors note that their algorithm, although not better in complexity, is faster in comparison with known algorithms for short braid words, and is almost independent of the number of strings in the braids.
0 references
braid groups
0 references
word problem
0 references
fundamental groups
0 references
diffeomorphisms
0 references
algorithms
0 references
presentations
0 references