{"entities":{"Q760501":{"pageid":762350,"ns":120,"title":"Item:Q760501","lastrevid":64210167,"modified":"2026-04-11T18:22:45Z","type":"item","id":"Q760501","labels":{"en":{"language":"en","value":"On the complexity of intersection and conjugacy problems in free groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3884369"}},"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":"Q760501$E68B3E2B-81C4-4D94-B8EB-48DF51389E5A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aa646bd7c3f253e138430525af4aabc9eeb67b43","datavalue":{"value":{"text":"On the complexity of intersection and conjugacy problems in free groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q760501$9A81CFFF-3D44-494E-A566-11D4F81C97FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"277174fe3c9499501565af2419cf9cc1ed21f68b","datavalue":{"value":"0555.20016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760501$9308F34A-BDDE-4738-9EA6-738AD021EBC7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"214ea9f02e9423a5a3f296fad24faec95fdad569","datavalue":{"value":"10.1016/0304-3975(84)90046-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760501$E9609F05-8FA6-4B59-92CE-6B40A4CADD0C","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":"Q760501$BE43D9B8-3D3E-4892-9DD8-3488F4F9B364","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":"Q760501$5F9D21DF-C553-421B-AB98-63F49889B1BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3396cd3d6f404fba4f2939f8f65a4f9ab5d09f83","datavalue":{"value":"This paper is a continuation of the paper reviewed above. Like its predecessor, this paper is aimed very much at the computer scientist. From the authors' abstract: ''Having a Nielsen reduced set of generators for subgroups H and K [of a free group F] one can solve a lot of intersection and conjugacy problems in polynomial time in a uniform way. We study the solvability of (i)\\(\\exists h\\in H\\), \\(k\\in K:\\) \\(hx=yk\\) in F, and (ii) \\(\\exists w\\in F\\) \\(w^{-1}Hw=K\\) and characterize the set of solutions. This leads for (i) to an algorithm for computing a set of generators for \\(H\\cap K\\) (and a new proof that free groups have the Howson property). For (ii) this gives a fast solution of Moldavanskij's conjugacy problem; an algorithm for computing the normal hull of H then gives a representation of all solutions. All the algorithms run in polynomial time and the decision problems are proved to be P-complete under log-space reducibility''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q760501$A500426B-59EB-4DFF-88BB-E9D924151B02","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e478659c80ac196196a2283c8b16b79c8d8cd8d5","datavalue":{"value":"20E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760501$299FC157-C989-4D87-AF35-C3D8DF7C6F67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760501$87A7B6BE-95BC-409B-86C4-0F6E9E49D4BD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"94700b2ac10fb0ad8230a2a134fd2bd6fec98387","datavalue":{"value":"3884369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760501$BB8CFBD0-66A3-4ABA-BAB2-77CA2A253615","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5da4688352172c129d523a84030ee0aa452addd","datavalue":{"value":"polynomially time complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q760501$03380C57-16FB-49A2-A2D2-E980B9FFE4BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d82eebb3cebf2f14f512e3f6d08d76a31b05c16","datavalue":{"value":"set of generators","type":"string"},"datatype":"string"},"type":"statement","id":"Q760501$8D7F80B6-BE25-4316-99E6-9706924171A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ffb9b557bffdfa5cd70d593a7ec3f8594345072","datavalue":{"value":"free groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q760501$B9272AD8-4067-42EA-A7A1-1275B77EEE61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71d1e996a17ecd8c9d7e5b54b268201adef66724","datavalue":{"value":"Howson property","type":"string"},"datatype":"string"},"type":"statement","id":"Q760501$9A31DD6D-3A89-48D3-895F-56BF5A363CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a63ee56c4d2f81c4a9b7f5e8124d077a3591e1b","datavalue":{"value":"conjugacy problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q760501$FEB3E55A-6214-41FF-8CB6-49115BAA022B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q760501$22814ED1-42A4-4990-9854-2982866059A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q760501$3D6247D3-2257-4743-ACC6-BF9E483A67FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40e3c57e99bba249e8c0684c003ef555ec3b144b","datavalue":{"value":"log-space reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q760501$5F101FFD-12BE-4E5F-A53F-513919B7065E","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":"Q760501$54FF2772-7CBF-427C-AAEC-2496D5178406","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":"Q760501$8F58480B-737E-40C6-B1BF-51891A1EF001","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":"Q760501$49E52A31-2158-4E31-A7D2-CB3740ADA439","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":"Q760501$A605C24B-FFC9-4707-9457-F96BABC5F0FA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea3fdd1aae113614604b042ac9379cf8e612e174","datavalue":{"value":{"entity-type":"item","numeric-id":3919078,"id":"Q3919078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760501$5ACC21A1-9F16-4F1A-9AF8-14CB9E9C26DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"299b5659273b8e93379bfd44a9f55f0210eeee53","datavalue":{"value":{"entity-type":"item","numeric-id":760500,"id":"Q760500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760501$CD059270-6248-4AA8-AE1E-4A521180C703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e13e8f1b5f1454f6b865214a30d9dcbfeb64f10b","datavalue":{"value":{"entity-type":"item","numeric-id":5828014,"id":"Q5828014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760501$C836A631-33BC-45CD-B5CA-A7D4D266E78C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"174ee42fe7758ee1fe3445c868379b623f538748","datavalue":{"value":{"entity-type":"item","numeric-id":1249228,"id":"Q1249228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760501$96D28392-8BF6-4DFF-AFED-242B3DB5762D","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":"Q760501$48C56757-0991-4259-BA34-A52A1DE1EE22","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":"Q760501$BE7C1DB3-4015-4642-A4E4-CAA6FCD428EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dff16dae7c253ebcf644e37555d10c67be45afe2","datavalue":{"value":{"entity-type":"item","numeric-id":2550073,"id":"Q2550073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760501$7AE3048A-913C-4403-8A0A-F36BFB3B0CA8","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":"Q760501$63CB81BC-0207-4E3A-8E72-A3E26EC59087","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f422724d148093401e511b345a22d054fa507939","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90046-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q760501$1A8518D2-C8AD-4F5A-9C2F-429EEBF9BFEA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"857bb0e3ade404dae408bf3cd348772943b407a1","datavalue":{"value":"W2020680034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760501$DBA37B8A-093C-47FA-AB8B-76FC94D2E092","rank":"normal"}],"P1643":[{"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":"f8f38077b38a99eec3a3a06194e73e86c41631e4","datavalue":{"value":{"amount":"+0.861770510673523","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":"Q760501$E1AF92FD-1E18-4E54-ADDF-2A505D1950F8","rank":"normal"},{"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":"3d53935b716e0aba633b8c066c62303ed0967514","datavalue":{"value":{"amount":"+0.8416539430618286","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":"Q760501$D4F7DF70-94BD-4489-8B7B-AB0D918F9340","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":"2bf7e95aec1e0c24d9c8557e5f18e959377b471c","datavalue":{"value":{"amount":"+0.8301461935043335","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":"Q760501$4C44D5E0-BCD1-430B-B2E9-25F3D5C5E16B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"118224084be1f0bf59bf6db8b6e68f1693cdb82e","datavalue":{"value":{"entity-type":"item","numeric-id":3791335,"id":"Q3791335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e347d7c0dbe01e89162feed9742abf7c14949c31","datavalue":{"value":{"amount":"+0.8249749541282654","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":"Q760501$461F6DA3-12E6-40AF-83B5-8A736ED3A1EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa8462fb3430a5fffd87e6ca26dd6858fea6307b","datavalue":{"value":{"entity-type":"item","numeric-id":358196,"id":"Q358196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c6b259da25db4d70afbb9b9e74cb65a1b1ac1d6","datavalue":{"value":{"amount":"+0.810749351978302","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":"Q760501$5B6C77F7-7096-4656-8E7B-246A3BAB9018","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of intersection and conjugacy problems in free groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_intersection_and_conjugacy_problems_in_free_groups"}}}}}