{"entities":{"Q951964":{"pageid":953812,"ns":120,"title":"Item:Q951964","lastrevid":57261651,"modified":"2026-03-27T16:50:45Z","type":"item","id":"Q951964","labels":{"en":{"language":"en","value":"Polynomial-time word problems."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5361851"}},"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":"Q951964$163BF932-79F1-4D3B-B1CD-458294E51AD2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"58ab35396896721c876ce850284b1bf5ac5a8d75","datavalue":{"value":{"text":"Polynomial-time word problems.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q951964$6A085FDB-2610-4DB7-ADCC-76E6BB0C0DC0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"879a33426c552c0db3e1c1312da243ec3021eeed","datavalue":{"value":"1172.20028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$7B65273D-58BD-4489-B5A0-142238D9527F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e1438264206e7a127996e633a35003c64f3b249d","datavalue":{"value":"10.4171/CMH/142","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$4CD2B2C3-BDBA-458B-AE94-46266BC166F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bcc3ecc210d1d2d3eaa22b55850fcf2d5c97ecc8","datavalue":{"value":{"entity-type":"item","numeric-id":433916,"id":"Q433916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q951964$CCFA4FE2-8AB1-4527-B94D-E6ADFAACA392","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"5fcb6cd43a0998d068add0035faca6247a2e2036","datavalue":{"value":{"entity-type":"item","numeric-id":185403,"id":"Q185403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q951964$FAFD650D-F95A-45E2-843A-27FB9FF194DD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"82c79b8a868479c39c5472830d24e23fa49d7c7b","datavalue":{"value":{"time":"+2008-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q951964$637FF022-54A0-4756-A592-3756C2E540D4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fcb500584f2bc7d26c10153bb4d1c783a6535b66","datavalue":{"value":"https://arxiv.org/abs/math/0608563","type":"string"},"datatype":"url"},"type":"statement","id":"Q951964$01642FD2-D496-41D6-97E2-833909E0069A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5e421cf0ccdcb29dca6dedffb8db4c31ff46fb19","datavalue":{"value":"http://www.ems-ph.org/journals/show_pdf.php?issn=0010-2571&vol=83&iss=4&rank=3","type":"string"},"datatype":"url"},"type":"statement","id":"Q951964$03FD6D05-534D-4CC2-984C-1A780266FDA3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d0b9f49a3d8cf31fc8f68a355e6a8112c0cd1d0c","datavalue":{"value":"The author observes that automorphisms of the free group strongly resemble straight-line programs, which are widely studied in the theory of compressed data structures in computer science. A crucial result by M. Lohrey is used that the word problem for compressed words in the free group is solvable in polynomial time. This theorem is applied to 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 handlebody subgroup of the mapping class group. The paper is self-contained. A detailed exposition of the necessary results from computer science including Plandowski theorem is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q951964$55575C4B-353D-403E-B244-FBDF27C1A565","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$CA7B6B1A-B693-4B58-8C83-D49BF869FACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e478659c80ac196196a2283c8b16b79c8d8cd8d5","datavalue":{"value":"20E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$14007164-9CC7-4EF4-ABF8-8FB1B88E173B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9f4783aefc0465a962c2651b89c22d3aa35c14ce","datavalue":{"value":"20E36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$70E0FBC2-E128-400E-80A0-804463597C01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$D493E836-074C-4EED-977A-49BE00DCB03A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f78d41e47725ec1bd07b77db78bbc1730df4db63","datavalue":{"value":"20F38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$206E993D-2664-4247-A7B7-79A89C77C535","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"21f00aab010cafc29f45ee659310afaf13c9d8f3","datavalue":{"value":"57M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$156FDFD4-6EA4-49FF-848D-9B78365AECDA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e0eef93951b901b4e19c5746ea2e91d9f99b62f2","datavalue":{"value":"5361851","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$67FC4837-F1AD-490E-A9BB-E911477E6742","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q951964$A809020C-658C-4195-905B-8E453A27B43A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff9f78089affef06c072081bb824e40f99a75bd9","datavalue":{"value":"efficient algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q951964$FBB1AC76-6077-4CED-AE67-0F0267C2AE0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8994690d72097b14ad1f9fcd4cee71a341baf3fd","datavalue":{"value":"automorphisms of free groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q951964$EEA61795-D718-4E3A-A325-6BC087726951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8acef8c5412877d7ff45210ae9d119deab5ead4b","datavalue":{"value":"straight-line programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q951964$BB028756-26FE-4843-AA37-B964D7FA07B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f8dd5c493bcfe457a2c05cd0b9ce65be151090","datavalue":{"value":"compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q951964$30328A29-1EAD-431E-8FEF-2D2EA3EEE14B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c2e2da5cbe64d37fcd4f5bec950d1d340c6d7bd","datavalue":{"value":"free-by-cyclic groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q951964$E637172B-6F01-4410-A6CF-D263334973C4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c75e46d52756574cc2c3b6666627a330102767ca","datavalue":{"value":{"entity-type":"item","numeric-id":338846,"id":"Q338846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q951964$17323116-D0A8-45AE-B555-C68060F6EDE4","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":"Q951964$FB80A357-635D-466F-818F-DC19D246E4A1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"210623c9f949bf95d66c3d7db2966cbb18c6ba4f","datavalue":{"value":"W2076505256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q951964$33B78415-45C5-483E-99ED-09185405510E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"baae7a2ae50c0cc18664aaf88d96f37cf8461f84","datavalue":{"value":{"entity-type":"item","numeric-id":3578449,"id":"Q3578449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82248f0509e405a4abf3776054118a0e72f99fdf","datavalue":{"value":{"amount":"+0.8686777353286743","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":"Q951964$698643AB-AA81-473A-95ED-4E863D945CE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58513931995d6600e6dfab8c79d65b2681ed0f58","datavalue":{"value":{"entity-type":"item","numeric-id":760500,"id":"Q760500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faa69d65775a18df74416ce9ea4553dd719ac41e","datavalue":{"value":{"amount":"+0.8448348045349121","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":"Q951964$37A83429-D6DB-4570-B30A-EE3E435A64E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4bc8dc4c106cc6391622f012a2df40246291af2","datavalue":{"value":{"entity-type":"item","numeric-id":5405102,"id":"Q5405102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"972c254256d40267cc2e1ecd8503f9550f33c450","datavalue":{"value":{"amount":"+0.8362888693809509","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":"Q951964$E5404B4D-C6D8-4975-81FB-CE40EFAF336A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac32ca5448c583794cf07d033ad8068f6e336abe","datavalue":{"value":{"entity-type":"item","numeric-id":3584895,"id":"Q3584895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b668dfde807a5d80d52a81dd4f89c00d1c903f1a","datavalue":{"value":{"amount":"+0.8290172815322876","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":"Q951964$FD29E40F-8220-4B16-89D8-9A1E231C2AE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fc5d64b8c1c2bdb9b7b44ebd1b9c4469727cf81","datavalue":{"value":{"entity-type":"item","numeric-id":4904513,"id":"Q4904513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10f2d6b4acadaa092be6932d215aa08529bb659d","datavalue":{"value":{"amount":"+0.8168764710426331","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":"Q951964$C2D642F5-18F9-4715-9948-19A363DE9E96","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:951964","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:951964"}}}}}