{"entities":{"Q974649":{"pageid":976497,"ns":120,"title":"Item:Q974649","lastrevid":65884233,"modified":"2026-04-12T06:01:52Z","type":"item","id":"Q974649","labels":{"en":{"language":"en","value":"The monomorphism problem in free groups."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5716896"}},"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":"Q974649$9962327C-8A8B-49C4-89B5-FCFB445985D3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e351527e0404d9e4e3e1b6a5e4053f799790716f","datavalue":{"value":{"text":"The monomorphism problem in free groups.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q974649$DFCC2790-C518-4ABD-B404-E0FE34A001DC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"30cb7d49534904285c93eca97b3bc69e9a421582","datavalue":{"value":"1198.20022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974649$AA0659AF-1A39-44E2-AD77-1B071E86EBD2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5db1cc0a9d5111404666f7aa89bf92d3cf23019d","datavalue":{"value":{"entity-type":"item","numeric-id":273096,"id":"Q273096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$C9B827AA-1AA6-43B7-BFAA-453C346B4AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fb3865199df4966b0a69793bf9b23f63f4d14f2","datavalue":{"value":{"entity-type":"item","numeric-id":506600,"id":"Q506600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$C2D225DB-07DE-4AE9-873A-598B79CB37B4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"db22232807c795272dc3a83fabf3be514df44f25","datavalue":{"value":{"entity-type":"item","numeric-id":166039,"id":"Q166039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$78605F8F-A916-4E41-96AD-43749C5338CC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6b8b8b9ed890274dddb65704ba3812ce7c13c4f9","datavalue":{"value":{"time":"+2010-06-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":"Q974649$C1F68B2C-2CB4-4400-8C05-2E5776029840","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8e8fe9a3aaf0897a52e754a0dbc33b624a4f346","datavalue":{"value":"https://arxiv.org/abs/0910.1899","type":"string"},"datatype":"url"},"type":"statement","id":"Q974649$B9D18F1F-5113-48E6-B3C3-AF632793ED96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"594ba3c0cabc9f2275da20926b58d3324540a818","datavalue":{"value":"http://doc.rero.ch/record/20227/files/Arch_mat.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q974649$DC219745-6987-4AB7-9E3F-BF646E90D0C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a2e674aefe13cf08fe07fd3b0899624690dd9cc6","datavalue":{"value":"Let \\(F\\) be the free group of finite rank \\(n\\). For two elements \\(u,v\\) in \\(F\\) we can formulate the natural decision problem: does there exist an algorithm that determines whether there is a homomorphism \\(\\varphi\\colon F\\to F\\) such that \\(\\varphi(u)=v\\)? If \\(\\varphi\\) is required to be an automorphism, an endomorphism, or a monomorphism then this is called the automorphism problem, the endomorphism problem, or the monomorphism problem, respectively. The automorphism problem for free groups was answered positively by Whitehead. Makanin's algorithm implies that the endomorphism problem for free groups is solvable.   In this paper the authors prove that the monomorphism problem for free groups is solvable by providing an explicit two-stage algorithm. The simple algorithm for Stage~I is at least exponential in the length \\(|v|\\); however, it is shown that this may be replaced by an algorithm that is polynomial in \\(|v|\\). Stage~II consists of applying Whitehead's algorithm. Whitehead's algorithm has been conjectured to be polynomial in the lengths \\(|u|,|v|\\), and this is known to be true either when \\(n=2\\) or when \\(u,v\\) satisfy certain technical conditions. It therefore follows, for example, that the monomorphism problem for the free group of rank 2 has a time complexity that is polynomial in \\(|u|,|v|\\).   The paper closes by extending the methods developed to prove that the multiple monomorphism problem for free groups is solvable. That is, for any \\(r\\geq 1\\) and any two tuples of words \\((u_1,\\dots,u_r)\\), \\((v_1,\\dots,v_r)\\) there is an algorithm that determines whether there is a monomorphism \\(\\varphi\\colon F\\to F\\) such that \\(\\varphi(u_i)=v_i\\) for all \\(1\\leq i\\leq r\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q974649$920A8B73-22C1-4DB3-84E7-1FDB930C4F4C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e478659c80ac196196a2283c8b16b79c8d8cd8d5","datavalue":{"value":"20E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974649$77E9F166-5277-4C5B-97EB-D89677453F22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974649$7CEB1CCF-79A0-4538-A4AF-D6A2D16C62FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9f4783aefc0465a962c2651b89c22d3aa35c14ce","datavalue":{"value":"20E36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974649$AB424D76-92D3-406A-948F-28E9B68B2149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974649$19ED6B69-B750-4B4A-930D-9164E6BAEC53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974649$561D9BAA-173C-49DA-A23B-5CB2AF99AC82","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bdb9e4fd0fe006397cfffaf3d386d5931b99595b","datavalue":{"value":"5716896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974649$D9EE6A61-B123-4E39-9B82-4C9128BFEDF2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ffb9b557bffdfa5cd70d593a7ec3f8594345072","datavalue":{"value":"free groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q974649$1FFBB313-8692-479B-ABC4-2F2447EBA2ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q974649$9D59B0E6-E828-4CF2-B768-DC59CE2A0DCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2278f035590e400c7ab8ae4076c4d373dd8d0ebe","datavalue":{"value":"complexity of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q974649$396C2490-D9A6-44EF-8D37-9877655CE781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e7fd1589c9f4197d35560ddd01f2e2a87d5b567","datavalue":{"value":"endomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q974649$369E7B13-1011-4316-888C-5EFFB9D73EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3f603c8f2ea854834df5612a8efdc4948a36da3","datavalue":{"value":"monomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q974649$FD427032-9A27-45CA-91DF-F53733C537C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q974649$40D04073-99EB-466A-97C2-06196F7C770E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff9f78089affef06c072081bb824e40f99a75bd9","datavalue":{"value":"efficient algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q974649$12D4EA1A-C7B1-4833-BB3B-0AD31C863DFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d85c121e6e6200a1d4667137fca957de2656737","datavalue":{"value":"polynomial time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q974649$8BDA8A03-2ADD-412A-B73D-BDBFD01DA7DC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f2ffab9587a4e6876d3bbdb56c67d1ab8a89cefb","datavalue":{"value":{"entity-type":"item","numeric-id":1861490,"id":"Q1861490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$B2FC31C1-4338-470E-889B-D415784B9BF6","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":"Q974649$AAD6F601-9F6F-4525-8F59-2320C8487536","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"848956453100da6c42ddbe173fe19559d41a083c","datavalue":{"value":"W2089269623","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974649$D1B96898-3ED4-4D1B-8FDF-E5EBFFFEC734","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"715525ad310b78d25a8c8ced18918e7f2060a7f1","datavalue":{"value":{"entity-type":"item","numeric-id":5297787,"id":"Q5297787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$8B6436E7-C940-4A9E-963D-10163C00C764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3237417c2bdb1dad38edfdf0e35161d25a71fac1","datavalue":{"value":{"entity-type":"item","numeric-id":1599084,"id":"Q1599084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$855B5F05-A57B-47A1-A52A-649C14754EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc396e5df6474de18265f2e9fb2e76146062c01f","datavalue":{"value":{"entity-type":"item","numeric-id":855970,"id":"Q855970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$3FD8F790-1616-4A3A-B330-1B07A76F0445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82d3cbffed8a301b84b1253490d8c6b17bf2e322","datavalue":{"value":{"entity-type":"item","numeric-id":4145882,"id":"Q4145882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$8B6AEC8B-5D39-4651-9772-9C0C79AF5AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"516799c82fb39c92923206092dc1c86efbfcb753","datavalue":{"value":{"entity-type":"item","numeric-id":4750010,"id":"Q4750010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$6F529CDA-21F6-49EB-A901-E8729ED2F666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95487a1f5300bb2c4be1e4a901d7b7167cc8f398","datavalue":{"value":{"entity-type":"item","numeric-id":1414027,"id":"Q1414027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$F3734213-4307-4B5C-A5BC-0847D946D996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dd841c5154c6f9ae7d4c069b19cb201b25a8825","datavalue":{"value":{"entity-type":"item","numeric-id":2503408,"id":"Q2503408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$C0CEA7FF-73CD-4DF6-9B2C-79D8AC043435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d2b66df2c8993b8c49e664896c0e26eb4d18fb4","datavalue":{"value":{"entity-type":"item","numeric-id":3502844,"id":"Q3502844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$4FCBA55C-D09D-461B-A133-6FE7DC047EFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3080d2d58a127e6277e9421ece0f2ec591b971e1","datavalue":{"value":{"entity-type":"item","numeric-id":3430309,"id":"Q3430309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$9E34F4E2-3467-4ADD-A3AF-686182D0B9F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75045873df38655043c6e681d2f3490613f9def8","datavalue":{"value":{"entity-type":"item","numeric-id":2645439,"id":"Q2645439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974649$77423116-E971-4660-B161-6671B90E8EEE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fd9fb1d22f9b2806c3bb7424e28541a4a497e0a1","datavalue":{"value":"10.1007/S00013-010-0118-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974649$93241D67-1132-4B61-AA16-8E0CA9B94188","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"debb74cabe664cf19dff2aa28578a24120fc5f03","datavalue":{"value":{"entity-type":"item","numeric-id":2759639,"id":"Q2759639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4466972be6b0395bc78d7ad8ec81554a63bfdd5d","datavalue":{"value":{"amount":"+0.865577757358551","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":"Q974649$CDEF35F6-3A00-4F1B-A574-58B836B60A63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89661843adbcbfb9cc862cb086b02fa8d1c5c459","datavalue":{"value":{"entity-type":"item","numeric-id":5297787,"id":"Q5297787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcba63ec5fdf5d29769c10f866f07c5982991be2","datavalue":{"value":{"amount":"+0.8411388397216797","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":"Q974649$697CF005-9B9E-44DB-95E4-A5C8548046C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"680d5a942f41d6ea9e23489cf43c7de74e76d797","datavalue":{"value":{"entity-type":"item","numeric-id":2518358,"id":"Q2518358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe551c42c9388b4cbbc4a3f4e6c2a7246db3d63c","datavalue":{"value":{"amount":"+0.83781898021698","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":"Q974649$C77D96E8-7B28-4A2D-8231-18DC64D14DF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d5afa26bfc50e8ab901ca0da6eb5dd8554e4e9c","datavalue":{"value":{"entity-type":"item","numeric-id":1414027,"id":"Q1414027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba026b4af82ac9b59ab28847b719f0e1cca9ae91","datavalue":{"value":{"amount":"+0.8143579363822937","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":"Q974649$784A5FAF-AB65-4419-8AE6-E28D48017F11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"625f7d3fe779c6118b32516169fbba9463e581ed","datavalue":{"value":{"entity-type":"item","numeric-id":3502844,"id":"Q3502844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49a8df57edb5ea96d4228162781c4c7c9f04b31a","datavalue":{"value":{"amount":"+0.8095365762710571","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":"Q974649$E582EBAE-FA6A-48AD-960C-78820BD96699","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The monomorphism problem in free groups.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_monomorphism_problem_in_free_groups."}}}}}