{"entities":{"Q1578891":{"pageid":1589631,"ns":120,"title":"Item:Q1578891","lastrevid":70750278,"modified":"2026-04-13T16:30:47Z","type":"item","id":"Q1578891","labels":{"en":{"language":"en","value":"On complexity of the word problem in braid groups and mapping class groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1501775"}},"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":"Q1578891$0CF350F6-FF48-4EB4-B5D1-3B8CF4DD00ED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"341fb15e9a28cd12ae8e974e27cfcda625fae9ae","datavalue":{"value":{"text":"On complexity of the word problem in braid groups and mapping class groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1578891$17CE8E90-6B49-4BB1-9641-1ED1E53F2FAD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1e67f7c9476601284c3ac935545272de730877ff","datavalue":{"value":"0967.20019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578891$D76E9275-3566-4E6D-9CE2-51285CF071DF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d95074963c88d62532c58ace8fdae7d10d300e8e","datavalue":{"value":"10.1016/S0166-8641(99)00063-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578891$FA8D5FFD-0091-4C87-91C4-81322D669284","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"459ade40737f8f2228c42d8e552526d690eb5bb7","datavalue":{"value":{"entity-type":"item","numeric-id":200602,"id":"Q200602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578891$CAF70670-B30E-4B42-98DF-23B0E91F81CB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"caed9871dffabe010c529575fe8b7c33d0847d94","datavalue":{"value":{"entity-type":"item","numeric-id":161372,"id":"Q161372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578891$DDBABB81-9906-48AB-BEB7-A03C4D50F2C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0c1d27f90c5efc0baf8dad41a96c8a8197323785","datavalue":{"value":{"time":"+2001-07-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1578891$A39C2117-7910-40DA-A965-5470412541D8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6dd182bc0ae63711d4b5766bed513a2538bccef0","datavalue":{"value":"https://arxiv.org/abs/math/9809154","type":"string"},"datatype":"url"},"type":"statement","id":"Q1578891$A8AF4AC6-E18C-483B-BA80-9BDD9144DB05","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"88d7a52212868099ba6ab9350511229f98ad2991","datavalue":{"value":"The paper deals with (uniform) word problems of the mapping class groups and other related groups. The author proves that the word problem of the mapping class group \\(M^p_g\\) of the surface of genus \\(g\\) with \\(p\\) punctures has complexity \\(O(|w|^2(g+p)+|w|(g+p)\\log(g+p))\\), where \\(|w|\\) is the length of a word \\(w\\), the complexity for the braid group \\(B_n\\) is \\(O(n|w|^2+|w|n\\log n)\\), while the complexity for the closed surface with genus \\(g\\) is \\(O(|w|^2g^2+|w|g^2\\log g)\\).   The author computes the complexity of the action of a given element of the mapping class group on the space of measured train-tracks on the surface. For the complexity of the braid group \\(B_n\\) he uses the exact sequences: \\(1\\to M^{n+1}_0\\to\\widetilde M^{n+1}_0\\to S_n\\to 1\\) and \\(1\\to\\mathbb{Z}\\to B_n\\to\\widetilde M^{n+1}_0\\to 1\\), where \\(\\widetilde M^{n+1}_0\\) is the extended mapping class group allowing permutations of punctures and \\(S_n\\) is the symmetric group of degree \\(n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578891$5FF02E95-ECB1-4FF3-A29F-656CA1E86105","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578891$2B16D36C-9CB5-4179-962C-EC652E6706A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"00c103224d34af523e7fce2ff3e40dd19709f84f","datavalue":{"value":"20F36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578891$339CF48D-A3CE-4DEC-98E2-88D788D7F545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f5206f46c6ca666840f8b4128198bef996fcacb","datavalue":{"value":"57M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578891$EFCBC855-583E-4E5A-9DCD-9F6245726D77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"adab020d252f1ca7f9815cc1cdbd7cf1e65b1f96","datavalue":{"value":"57N05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578891$AAD78D4C-B19D-42BE-A43C-963A5CE9AC6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578891$47A6A00E-5FCB-4DAD-A336-085193437397","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7c08df88084c741522aab42858a438f2a757cbb4","datavalue":{"value":"1501775","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578891$BF482F62-2B0D-4326-AD9D-3E8E35A2D31B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ba259c5c06af63100955fccf8bc8b370e89eaee","datavalue":{"value":"word problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578891$E393374E-3B1F-4821-8A44-96D2E974EBEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cb457684d6de0429861805f4366e89ef535b625","datavalue":{"value":"mapping class groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578891$93DE1924-019C-416D-BF63-E254710B9B3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42884d684a0db176107a7461dc06f6654a79f4f1","datavalue":{"value":"braid groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578891$76D0F6F7-529E-4CFA-B6C2-5BC12DF515CD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7eb34a5913e32e2432a47344f3fe5b5428d3d6a3","datavalue":{"value":{"entity-type":"item","numeric-id":441852,"id":"Q441852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578891$F6083DC6-4024-4E78-ACF8-42D42A425426","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":"Q1578891$6A8AB461-AF5C-490E-9C3E-B88A6572B1A5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d1aebb2a93949a56f3c29683fd4689abecb8b1a8","datavalue":{"value":"W2000638036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578891$58284242-D26D-44D0-8226-E3E71A282C0E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f45beb318fc7a8ea20c4d207595eb439e17a492f","datavalue":{"value":{"entity-type":"item","numeric-id":3788192,"id":"Q3788192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2c5823a3a2338b30f27cd741d0e2ff4a1dc4174","datavalue":{"value":{"amount":"+0.7886356711387634","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":"Q1578891$D6B629FC-1461-4867-A2EE-313841F4C133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2eb498058c9b455a550dfdc86433fe3150604d88","datavalue":{"value":{"entity-type":"item","numeric-id":4867139,"id":"Q4867139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1c63df28d23c8f3e6e1954c98ed17e2d0848ca7","datavalue":{"value":{"amount":"+0.7868573665618896","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":"Q1578891$8275AF22-2904-4BDB-B801-4DACB3DF7899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb28ab5ff14400b5fe718a56cbb14288b82195a2","datavalue":{"value":{"entity-type":"item","numeric-id":1604340,"id":"Q1604340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88e49ddae3175f463388c0df5cc2c6916c4ccf38","datavalue":{"value":{"amount":"+0.7794959545135498","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":"Q1578891$EA3772F9-1E02-4B55-98A4-8422B9660DEB","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":"3a7969b5cf6c30ee9ec7f5e13d7637ff9e6ae60d","datavalue":{"value":{"amount":"+0.7716615796089172","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":"Q1578891$ED9D2BA8-829A-4A0E-B653-D2EAC78AA432","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On complexity of the word problem in braid groups and mapping class groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_complexity_of_the_word_problem_in_braid_groups_and_mapping_class_groups"}}}}}