{"entities":{"Q1604340":{"pageid":1615080,"ns":120,"title":"Item:Q1604340","lastrevid":70956711,"modified":"2026-04-13T18:29:30Z","type":"item","id":"Q1604340","labels":{"en":{"language":"en","value":"A new algorithm for solving the word problem in braid groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1763530"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$B9C4DABE-BD9C-4C42-A324-53EB92CAF274","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f05be5818535e40b487df71a3edc21374d1971bd","datavalue":{"value":{"text":"A new algorithm for solving the word problem in braid groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1604340$4FAAB485-BDCB-43A6-BAB1-724C77C37281","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8dfc8327c6d3c30eec174505cdb27d1dfc954ba8","datavalue":{"value":"1008.20027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$45C48B60-B945-4622-9036-33E4D23B39FD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"403f963f8def6c721f1b950241d5076e268c0578","datavalue":{"value":{"entity-type":"item","numeric-id":394814,"id":"Q394814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$58986AD7-C4F1-4D68-BD7A-3BFDEDF0EA10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d4f8fa164e35dd6d77a3c6dc220b9f07b989787","datavalue":{"value":{"entity-type":"item","numeric-id":405225,"id":"Q405225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$2EF96454-1414-4FBD-B27C-BF9D24497A52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c7cf16dcf02d911fec60baceff72f24415a6d8b7","datavalue":{"value":{"entity-type":"item","numeric-id":817242,"id":"Q817242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$A2CF5022-B2A3-4928-98E3-614871016EB4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"87fedd43d9515b94c7651de65777aba7be17422f","datavalue":{"value":{"entity-type":"item","numeric-id":165833,"id":"Q165833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$DF680C9A-AA49-42A4-B3B3-670D3D131551","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"adb3ef540eac58911e63cf63f703d86d64686cb2","datavalue":{"value":{"time":"+2002-07-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1604340$089BD311-BC5A-412C-AF99-604D7731858E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"14098fb2dd7a22f66d48b55e5ad0b024d78000fd","datavalue":{"value":"https://arxiv.org/abs/math/0101053","type":"string"},"datatype":"url"},"type":"statement","id":"Q1604340$5393D603-5668-43A0-8F4E-D0629821433B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"56b4ddfcddd678b9fc3ce3ef08d11f25a6569a80","datavalue":{"value":"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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1604340$CA9BC3A7-9DBF-4D2E-A9DD-34187EC57EBC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"00c103224d34af523e7fce2ff3e40dd19709f84f","datavalue":{"value":"20F36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$A1E8AFC3-D599-4784-A29E-6F4F41D2F154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$52C415B2-FEBD-4361-90FE-0B3ADC9D225D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b90db52ca12088dc08c74afaecb99f82acc3eec","datavalue":{"value":"20F34","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$7CF14803-DEF8-4644-9FCA-9E0B2DB27B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"21f00aab010cafc29f45ee659310afaf13c9d8f3","datavalue":{"value":"57M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$2D8B0457-737E-4584-979E-E515DC31D1A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f96720fe29e309c34c82deec20bd95823bb71652","datavalue":{"value":"20-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$D14C59F5-923C-442A-91D5-465B415B56A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$11054A79-6028-4703-AD28-5E1BBB0F3FF9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aae1ea0c69d6d6b71aac4fd512b23857053a8114","datavalue":{"value":"1763530","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$5F9EAE0A-72A6-438A-92EB-74A055BE9EA0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42884d684a0db176107a7461dc06f6654a79f4f1","datavalue":{"value":"braid groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1604340$9E0A3867-B518-40C0-8942-CFDAC32B4299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1604340$9A4D2F74-C44C-4209-AAC6-8096E9C3FD9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86b10d51bd74d748506115d31f2f26a17ef98055","datavalue":{"value":"fundamental groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1604340$FC748517-9E7F-42B7-B0D0-16A267E1F2EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e42ed0fb014e29f90f152abcdc8c94d2bfcdeb67","datavalue":{"value":"diffeomorphisms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1604340$A2124A0E-A908-4E9F-B141-DAF4712EF527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1604340$FC1E129F-5259-4BCE-A825-A2309DD5AA03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e230deab86b759c7a9e477b6f36eb01e4e4db2f","datavalue":{"value":"presentations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1604340$5E991FC8-AF82-4FE7-89C0-0480021F0E3B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7a760754899c4252076421c1bbdd70a575016d7","datavalue":{"value":{"entity-type":"item","numeric-id":593287,"id":"Q593287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$6472346C-3928-4A87-9658-E0A2B8176C55","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$F73728CD-E853-4425-A8F0-49ABC1797681","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5b98795f4e50004f91fc640d68c7c7b82fa56517","datavalue":{"value":"W2053986282","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$FC3984C3-4849-4B0D-ABC7-82A387A24B0A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3b2f0df0870ace02365e18bb60dafa2acdb06f6","datavalue":{"value":{"entity-type":"item","numeric-id":2647600,"id":"Q2647600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$3A9F49A6-5673-4FA7-87D7-901CF215DD31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0854ffba55913ad2a7ece15cb79fd713df28328a","datavalue":{"value":{"entity-type":"item","numeric-id":1273842,"id":"Q1273842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$5471A9C1-2314-4C14-8A50-9F6553AE75B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be5eeda466d1de50010d9b5edb0eb621f65a787","datavalue":{"value":{"entity-type":"item","numeric-id":4310780,"id":"Q4310780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$1989864A-DF7B-44A7-9788-60039C7CF730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d1aeb29a15bbc3c5df5b92b06c3556ae70c4d5b","datavalue":{"value":{"entity-type":"item","numeric-id":4837966,"id":"Q4837966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$86E5837E-CB9F-4995-9DEE-D829F52C4C29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac593b8d844f289785c5bca4b3e44139f06bd56b","datavalue":{"value":{"entity-type":"item","numeric-id":675872,"id":"Q675872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$B15B98FF-4B12-48A4-BAFC-449BFE3232A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cf3df66a28ebe9fcbe07b6acc85cf95b3b5e1f6","datavalue":{"value":{"entity-type":"item","numeric-id":4322220,"id":"Q4322220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$8E8C0633-F6B4-4C83-B6C8-8C20A495BC3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11bd07908756e386c3973a11b7db826c43296896","datavalue":{"value":{"entity-type":"item","numeric-id":4949387,"id":"Q4949387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$9F7DDD44-C7FF-4BA2-9260-BDD714A4ED83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508f54be2c5b75efb9d7c6ca2484ac0fb2a9266e","datavalue":{"value":{"entity-type":"item","numeric-id":5589369,"id":"Q5589369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$D23DD80E-DEF9-4562-95E9-28D585DCA216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f20cf6b8ea4a4ad9d0e48689da5d0eb19e3f630","datavalue":{"value":{"entity-type":"item","numeric-id":1578891,"id":"Q1578891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$6C442F0B-0DB4-43CA-AB1A-601A904DEF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62f6b7952aaf884b21f742a8cba1d4330c8db996","datavalue":{"value":{"entity-type":"item","numeric-id":914192,"id":"Q914192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$97C200CD-1F00-4DC5-BCB8-A2A74944F3BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26a91720db45c6507618307f557e250a087329fc","datavalue":{"value":{"entity-type":"item","numeric-id":1361367,"id":"Q1361367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$5BF09C85-94C8-4DEB-B319-2BA0AD3D7002","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c3a47966a29e98b4ef98ddc1672b293d86fe3a5","datavalue":{"value":{"entity-type":"item","numeric-id":3828120,"id":"Q3828120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604340$901CA47B-4D3E-4DF9-B590-06BEFDE1765D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a3322158054ea2aeff07eb9f29e3c35896653e37","datavalue":{"value":"10.1006/AIMA.2001.2038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604340$9889D24C-7434-4785-906B-6DCBA2ACF210","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f792d8dda0a76d06f3dbb81bd022c15a567baabc","datavalue":{"value":{"entity-type":"item","numeric-id":4432490,"id":"Q4432490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25dec0db48f4fc08e17acd0bf634b1aad65b0630","datavalue":{"value":{"amount":"+0.8880349397659302","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1604340$D0AD5F97-29DF-43FC-9A1E-2E6E1510CA4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3021bd6386515fa9d1702d5d2ef8e69e81568b7a","datavalue":{"value":{"entity-type":"item","numeric-id":1273842,"id":"Q1273842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0485e79345caadf6d8734ffe2cc659e563b0b2df","datavalue":{"value":{"amount":"+0.8786958456039429","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1604340$6BE7D190-2062-4BCE-856D-36C17B14FABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc289aad7c7a08a956571c43544accb55c638cf7","datavalue":{"value":{"entity-type":"item","numeric-id":4629388,"id":"Q4629388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e85e06290a89a6b8dcb867c6803f7273ab2b4c0","datavalue":{"value":{"amount":"+0.8757285475730896","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1604340$DDB78C97-E2FD-406D-8865-779846C3B28C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d30dcd7f6c7cf4d2b0da7aa8cdf5430e92784f7d","datavalue":{"value":{"entity-type":"item","numeric-id":914192,"id":"Q914192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"309cb593325b111543b9b163196078c0181bd433","datavalue":{"value":{"amount":"+0.844771683216095","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1604340$ED20580F-BAD8-4B24-85B9-F4E1BC9917E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87926a2f3666fd70e97c5c160ae244fad5cd43c7","datavalue":{"value":{"entity-type":"item","numeric-id":4322220,"id":"Q4322220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2fc0c6a9dadfdbaee0a422d578cbe0434a9b1de","datavalue":{"value":{"amount":"+0.8442898392677307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1604340$941DC0BA-8590-488F-A73A-82CC4780FD9E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A new algorithm for solving the word problem in braid groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_new_algorithm_for_solving_the_word_problem_in_braid_groups"}}}}}