{"entities":{"Q760500":{"pageid":762349,"ns":120,"title":"Item:Q760500","lastrevid":64210158,"modified":"2026-04-11T18:22:45Z","type":"item","id":"Q760500","labels":{"en":{"language":"en","value":"The Nielsen reduction and P-complete problems in free groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3884368"}},"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":"Q760500$FCEC728D-A46B-4C45-91B3-CAB7E6C3B35A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"09c9391d6436863a7e31bc5a865d8a154458a783","datavalue":{"value":{"text":"The Nielsen reduction and P-complete problems in free groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q760500$592985E7-5F12-4A38-820F-7E70594B2BAD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"018ff9c362474d31ca518fe50ba7aed658b471f6","datavalue":{"value":"0555.20015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760500$11E42AA9-FF64-4D11-BE10-7523FFE974DD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"83f9ed0bcd0d672d09b4fd9f84ea6925eca93b2f","datavalue":{"value":"10.1016/0304-3975(84)90024-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760500$3CF6FCB7-B326-4C75-8154-7696DD9C42E0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$CBA62C37-46B6-4CBD-BE7C-A593AB7EF729","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q760500$FE5CCA7C-80F3-4394-9DDC-49F2A4620F1F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c9288c820f9041790ff0bfe011fad7c88f70faa","datavalue":{"value":"This paper is written very much for the computer scientist. The authors consider various problems concerning free groups, such as: the generalized word problem; the determination of shortest coset representatives modulo a given subgroup; to decide whether two subgroups are equal or isomorphic; to decide whether a given set of elements freely generates a subgroup, to decide whether a subgroup has finite index. They show that these problems are polynomially time complete under log-space reducibility. The main tool used is a careful analysis of the Nielsen reduction process.","type":"string"},"datatype":"string"},"type":"statement","id":"Q760500$11820614-0624-4CC2-A814-A6D7A28897FF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e478659c80ac196196a2283c8b16b79c8d8cd8d5","datavalue":{"value":"20E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760500$5A2A3698-BAFD-4004-B693-73AAD7ED249B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760500$D66BDD5F-8214-4F3A-9D12-EF13F95996A3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e71224e2642447f1b88fbc7e16fc51b636c15b9","datavalue":{"value":"3884368","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760500$B9E1B1BB-8253-4400-9A78-EFF5BDB2BE50","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ffb9b557bffdfa5cd70d593a7ec3f8594345072","datavalue":{"value":"free groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q760500$C260B324-A2EE-43EF-BDFA-EA83E7E72912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38f4f6f4d088539378a28886a7c29fd41df02ccf","datavalue":{"value":"generalized word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q760500$EABC091D-C541-4690-A973-84A93AF03ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c2c5fbeca48be674ac30798d98d22f63f2d3c86","datavalue":{"value":"coset representatives","type":"string"},"datatype":"string"},"type":"statement","id":"Q760500$FA4B00DD-01E4-49C4-9374-97EDFF9A625B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5da4688352172c129d523a84030ee0aa452addd","datavalue":{"value":"polynomially time complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q760500$AD189374-5F05-4314-8BF8-E197211623BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40e3c57e99bba249e8c0684c003ef555ec3b144b","datavalue":{"value":"log-space reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q760500$E2E34646-F6CD-4F6C-8240-B1E714917550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be0fa90b500e1c651b0dbff895b85d4c4e0df0f8","datavalue":{"value":"Nielsen reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q760500$476EA0A2-E40A-4B28-8F41-6149FB0A57C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca21ff7d743cf6b0902f40630f2a6ab3da1a616c","datavalue":{"value":{"entity-type":"item","numeric-id":174769,"id":"Q174769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$046033DD-F676-47C6-AD6B-D68162416266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6a6cf0affc0bd3d92ff91b52146889f0c8e6de8","datavalue":{"value":{"entity-type":"item","numeric-id":580493,"id":"Q580493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$E4778723-EA65-4D2C-83BA-94DC643CC540","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c1f8efa98d174442e10aedd012e65f1e103dddb7","datavalue":{"value":{"entity-type":"item","numeric-id":531925,"id":"Q531925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$34887767-D37C-4942-85DF-03FCA4E82161","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":"Q760500$AEA8E760-86E2-4E00-9BD1-E539CDAA26B3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1edae5638c2d9788e9eeda3293472e05a195347c","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90024-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q760500$1719256B-BCC7-43BC-AE6B-DD7CE86A7EBE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3b3ed9a3dee1a37d159b88ea0cd66b2e964a34e3","datavalue":{"value":"W2002522693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760500$38666076-62BF-4DBE-8B5D-415365B79632","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4d0787b1cc5b37ced50aeab4d936b4e054af97e","datavalue":{"value":{"entity-type":"item","numeric-id":3659975,"id":"Q3659975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$0986D470-E2B8-4C1F-9B63-A403B2FF0C50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ccd7948f3fbfc247f30bb74f47dd253cfdd83c3","datavalue":{"value":{"entity-type":"item","numeric-id":4179012,"id":"Q4179012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$2B338FF4-345E-4C92-82D1-3F01E969B97F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6246b2ec5bb6c6049338d5f591c3f89ab996dfc9","datavalue":{"value":{"entity-type":"item","numeric-id":1243275,"id":"Q1243275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$EFAC6BCA-1130-4F64-BEFB-0EBB76FB9B9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd2de398d7faf4eeff3f07d94f0ba23ec3d66fb2","datavalue":{"value":{"entity-type":"item","numeric-id":4336265,"id":"Q4336265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$2530196C-FAE1-4218-9A4C-45EB0E96CFC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f547a1122c2a57190118ef4a8bd15bb3b54c79df","datavalue":{"value":{"entity-type":"item","numeric-id":3340146,"id":"Q3340146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$233465A6-9F4D-4A46-9E8F-72F2585B4153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"373c65ef4069b52a23fe230e08a271e32f56a00a","datavalue":{"value":{"entity-type":"item","numeric-id":1235982,"id":"Q1235982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$88DE7AC6-D510-45CD-A1FF-9C83C3452FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"175989e512d6162d2e23de4539fb227c102249ff","datavalue":{"value":{"entity-type":"item","numeric-id":4131647,"id":"Q4131647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$BE19A26C-93EB-4544-BF9D-2346687ADBB9","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":"Q760500$5C28DB30-11C5-4D3A-9AFA-A73386DB67EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b20cfc018ab6e5a56059403136b49d5687c82de8","datavalue":{"value":{"entity-type":"item","numeric-id":4135772,"id":"Q4135772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760500$3C210E58-CC97-486A-99BC-99FB3313A714","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8891b80e1ce0c66b720a791a130c06450c188c79","datavalue":{"value":{"entity-type":"item","numeric-id":3340146,"id":"Q3340146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"903311050160bf23dc34735fca5491671b3ef622","datavalue":{"value":{"amount":"+0.93643415","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$109B747F-5A10-4DD1-8CFF-562B1497A6CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dc71d82f2947ac04ab6480a82975a66db087c1c","datavalue":{"value":{"entity-type":"item","numeric-id":3971257,"id":"Q3971257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61e373aa14c896d38c65dacda07030e7e512a138","datavalue":{"value":{"amount":"+0.9274607","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$E313563D-DDC1-4127-9A40-4C0295120BC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4b84d4a71401e923e7ee4d0ad727f9b42435d97","datavalue":{"value":{"entity-type":"item","numeric-id":3816239,"id":"Q3816239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8c3fea2a73ec36d423a21027ef327339aedf79a","datavalue":{"value":{"amount":"+0.91845334","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$0E249EC0-B6FA-4206-80F2-1D33F3E24BB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"378395b1fc328af223359d6b26fdf82d507e6000","datavalue":{"value":{"entity-type":"item","numeric-id":1086673,"id":"Q1086673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61afc6f0c2970d2cd0d7c082563fd12572694618","datavalue":{"value":{"amount":"+0.89417636","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$39026EA6-C945-40C4-A406-70A36C1D2FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"417f05cfcd8def9ce36caefafd920cc0ccdd9c58","datavalue":{"value":{"entity-type":"item","numeric-id":4696706,"id":"Q4696706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4186e75e6c4314cba1f3757d8ac2d11fc589653a","datavalue":{"value":{"amount":"+0.87969","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$233496A3-4DFC-45A2-B00A-D61195DD7C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e568ca3e714bbdad3fba94e610a5a00ce2e7a8d2","datavalue":{"value":{"entity-type":"item","numeric-id":2317679,"id":"Q2317679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f6189654029db072cb9daf0030cc679e607dab3","datavalue":{"value":{"amount":"+0.8790679","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$D473D88F-FBF8-451F-B4E7-01B5C55FBD0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1e8fcc69be2eec5ca1587154e2f0ebd761a665a","datavalue":{"value":{"entity-type":"item","numeric-id":1755896,"id":"Q1755896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ebd301bfd3e93d77cd854dde89e753770345a46","datavalue":{"value":{"amount":"+0.8786221","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$CF4689E0-6E7B-4A5F-9671-292B0C9C171F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f51efc0a15b25cc09a6b3838971fcc41ec7156f3","datavalue":{"value":{"entity-type":"item","numeric-id":1821866,"id":"Q1821866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2db8c326ddd236d4a8ec37d8940f4dff0e6db33d","datavalue":{"value":{"amount":"+0.8774227","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$1CFE8386-597F-40DF-A358-0EAE9E30A22C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bcb2525cede533c7400f2b3f64ebeffb37d208c","datavalue":{"value":{"entity-type":"item","numeric-id":4224319,"id":"Q4224319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e51df3888d506e1d1a8f02837cd783f1c40d37a6","datavalue":{"value":{"amount":"+0.8747953","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$4584367A-F87D-4CD2-BBEC-574521CAD36F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51183160268480f0601d444b711faea175f1f5f0","datavalue":{"value":{"entity-type":"item","numeric-id":4632433,"id":"Q4632433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7787c2f8761a0f83ec6f07bbe7aa27aa81a2338f","datavalue":{"value":{"amount":"+0.8747908","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760500$8F624199-6B78-434A-8E0B-D25B05F3AFB5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Nielsen reduction and P-complete problems in free groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Nielsen_reduction_and_P-complete_problems_in_free_groups"}}}}}