{"entities":{"Q1899162":{"pageid":1909904,"ns":120,"title":"Item:Q1899162","lastrevid":71108910,"modified":"2026-04-13T19:32:16Z","type":"item","id":"Q1899162","labels":{"en":{"language":"en","value":"Subsemigroups and complexity via the presentation lemma"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 802562"}},"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":"Q1899162$F909E6B1-2DDD-49F1-B26E-5EA5E2F5A691","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"252bc8ab0c397b5fc0952fbe234282fec839abb3","datavalue":{"value":{"text":"Subsemigroups and complexity via the presentation lemma","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1899162$0BDB0341-0289-49EE-A414-172314E19AAF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f412ede6216ee295419ed1f95d4f8a30bbfef1d3","datavalue":{"value":"0836.20081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1899162$D34B9B09-5C75-455D-B97C-ECBAA223A82A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"19ff979f4a724a66ea278dbe0435b8ce90571428","datavalue":{"value":"10.1016/0022-4049(94)00063-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1899162$557F436F-EDC6-4553-9DAD-BB65C438EA5D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca3f0aafb4a65131574578897946ad1b54ef4d4f","datavalue":{"value":{"entity-type":"item","numeric-id":1899160,"id":"Q1899160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$4F4720B8-A13F-4D5D-91D8-1BECFE16E023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f7ad990de5ddfa4e0ce911e54e1411e5a5513c5e","datavalue":{"value":{"entity-type":"item","numeric-id":805744,"id":"Q805744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$055B3470-1E30-4416-9B57-B60102052327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ee0d24e0f2c78b3b28f7f633a110f4aa5cc774a","datavalue":{"value":{"entity-type":"item","numeric-id":494060,"id":"Q494060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$711F4E19-B161-4CDC-B83A-7906671F99EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"380e690bd7fd3f03733dccc956b7bdfe526b3550","datavalue":{"value":{"entity-type":"item","numeric-id":1401333,"id":"Q1401333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$C88AD45D-7767-4324-8599-64B6683B1173","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"34a2791b3d9645796ba9cdff19dd05bcf40f0161","datavalue":{"value":{"entity-type":"item","numeric-id":168348,"id":"Q168348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$0A8F4E99-49B1-4734-9519-AB414FB9CD2C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c4e5afb6084c75f4f8878bb3bd337019ced071d","datavalue":{"value":{"time":"+1996-04-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":"Q1899162$C3E15F8A-3A4B-4128-B3C0-A9F2DECD02EA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d2896a3ccba6579cf679e4c7cdd2eb1b92efb157","datavalue":{"value":"The Krohn-Rhodes decomposition theorem implies that every finite semigroup \\(S\\) divides an alternating wreath product of groups and finite aperiodic semigroups. The least number of group factors in such a wreath product is called the complexity of \\(S\\) and denoted \\(Sc\\). The problem of whether there is an algorithm computing the complexity function remains open for over the past thirty years and has motivated a considerable deal of research in finite semigroup theory. The conjecture that \\(Sc\\) is the maximum of all \\((eSe)c\\) where \\(e\\) ranges over the idempotents of \\(S\\) was proposed in the late 1960's, being verified in the completely regular case. \\textit{J. Rhodes} [J. Algebra 49, 1-45 (1977; Zbl 0379.20054)] gave a counterexample with four non-zero \\(\\mathcal J\\)-classes. To obtain it, he was guided by the Presentation Lemma, a technical result relating complexity of a semigroup \\(S\\) having a \\([0]\\)-minimal ideal \\(I\\) with a nontrivial group such that \\(S\\) acts faithfully both on the right and on the left of \\(I\\) (called a group-mapping semigroup) with the complexity of certain associated semigroups via a coordinatization of regular \\(\\mathcal J\\)-classes and the action of \\(S\\) on them. In the present paper, the authors give a proof of the Presentation Lemma and a categorical formulation of the lemma. This leads to the verification of the above conjecture in several cases, where some technical definitions are left out: (1) when there is a unique maximal \\(\\mathcal J\\)-class among the regular ones containing non- trivial groups; (2) for almost-disjoint semigroups; (3) for overlapping monoids; (4) for semigroups with at most three non-zero \\(\\mathcal J\\)-classes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1899162$DED614A8-812A-47E4-94DC-75BBAD833865","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1899162$035837AC-481C-44AA-B9F1-A5EAC89E45AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"da4486fba5293e43f43fa118be7b2896ee43bba4","datavalue":{"value":"20M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1899162$3E84824A-073A-457E-8EFF-828D0C4289C0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1bb9156cd7e2069cfac3edae2a63f99522c36070","datavalue":{"value":"802562","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1899162$F3DCE683-89F8-4817-B4D1-D23023E7B744","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92c1756ce19d6469dbbe7d85a48e7db6f937499d","datavalue":{"value":"Krohn-Rhodes decomposition theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1899162$797F0710-6165-43DD-9BD5-46D294D469B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f531b0e0a828fa7a37e8a4a90f6c1f6ca89420f2","datavalue":{"value":"finite semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1899162$8E5B3777-1B67-44B4-B99B-66CD29A995EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f902123376434aad9d2469d920797379acf92f40","datavalue":{"value":"alternating wreath product of groups and finite aperiodic semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1899162$33D1D8CE-E390-464E-9FA7-40905A374783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1899162$1ADFDFB9-3F8B-4709-85B4-3C59186AEE29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae2b2952403bc9913b13b364ff2ee4a26166f3b9","datavalue":{"value":"idempotents","type":"string"},"datatype":"string"},"type":"statement","id":"Q1899162$DCC262BF-FC89-44C2-9B26-8014C7C7B89C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e260ffaf087f4b161d3cc1b58c45c117d316801d","datavalue":{"value":"regular \\(\\mathcal J\\)-classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1899162$5607833C-EEC2-47A0-8B22-FC6880D7C408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da846e90a0bedb4c05feb3fd61890311df97cda4","datavalue":{"value":"Presentation Lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q1899162$DC057C59-4C8C-4D57-88C4-FDC65C89956E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99980a1fe8b67be8570894d1f605195f6f2e1e0e","datavalue":{"value":{"entity-type":"item","numeric-id":375866,"id":"Q375866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$855E90C7-F65C-4751-A840-811B6C95C0AD","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":"Q1899162$A1C0CF50-70D8-4D84-A4AC-95BF741B8454","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"058738fd32a34da2a451bc1b2b187350f96bb04c","datavalue":{"value":"Q124910146","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1899162$2F15F432-F379-400D-BBC2-A854DF8BEAC6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5afbf744a209bae591f2001b963f84ed85dc6a7","datavalue":{"value":{"entity-type":"item","numeric-id":3848243,"id":"Q3848243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$7C1903FD-472E-41F1-88CA-B25E7E1A3B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daa28b36f1d47ef725ba4acb380f1839600a6b45","datavalue":{"value":{"entity-type":"item","numeric-id":4132170,"id":"Q4132170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$B26A166D-D617-41E7-8DE9-D322D678893E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de840207ef12d35e5596885c4b64620446878d6c","datavalue":{"value":{"entity-type":"item","numeric-id":1824040,"id":"Q1824040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$8E808177-7786-4D75-AD5D-1029D317DDD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a521ff917a6cc40526a507e473e4cb5a8e35a41","datavalue":{"value":{"entity-type":"item","numeric-id":4872073,"id":"Q4872073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$E5C9AB59-18D6-4E05-95C3-8B0131DFC5F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a771da5a4143614d66e61e5eb1c065796a9fe46","datavalue":{"value":{"entity-type":"item","numeric-id":4126563,"id":"Q4126563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$5262752C-7042-48AD-BDD7-99EA59B2194D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afe18fdfb882c799d34a7482b763d96a45625e71","datavalue":{"value":{"entity-type":"item","numeric-id":3853827,"id":"Q3853827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$AE2CE7BC-E278-4134-A990-CDE7A289146A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adea85490b3f1a14a66925725a7b152056733cb4","datavalue":{"value":{"entity-type":"item","numeric-id":1247497,"id":"Q1247497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$13444C6B-710F-452C-AFEC-B7C8655E6AF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76e8ded65b4ee32368612cd00c287faa9bf6bf30","datavalue":{"value":{"entity-type":"item","numeric-id":4263906,"id":"Q4263906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$1699787F-A586-4E7F-A2E3-94B6BCBAAE9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4106ee1359f86fe88fb498711e75cf06db6594e","datavalue":{"value":{"entity-type":"item","numeric-id":581545,"id":"Q581545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1899162$7EA97A3D-1F69-4195-87CB-B91B7996030F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9441db796ce8348f7f0f09bf656c0465a00cccce","datavalue":{"value":{"entity-type":"item","numeric-id":5493859,"id":"Q5493859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1889eff952443367bc1a068c3114e006ae430c67","datavalue":{"value":{"amount":"+0.7806422114372253","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":"Q1899162$5C5CC20A-C451-479A-9786-9768D9983711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11e2d6f085ea02faec2bf8399b0f00eff7524671","datavalue":{"value":{"entity-type":"item","numeric-id":1941297,"id":"Q1941297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9579d0f6b46abc835bd534a0070230a0b3e64489","datavalue":{"value":{"amount":"+0.7793510556221008","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":"Q1899162$5D62F3A7-A682-48AA-A2B0-773857C305F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ac8c347224563c9ff89c076d6891935aa488d6a","datavalue":{"value":{"entity-type":"item","numeric-id":2505011,"id":"Q2505011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15b3127af666d6eb1bca6e788534c650877a2fc7","datavalue":{"value":{"amount":"+0.7654189467430115","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":"Q1899162$31B67511-D8F5-4EED-80D6-612C8BE4B33E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1846e82d8acd164fbc491568ad58cb8d06dffe7","datavalue":{"value":{"entity-type":"item","numeric-id":4942266,"id":"Q4942266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20316ec0e59c41baf48cc98cfc80a72617959310","datavalue":{"value":{"amount":"+0.7523789405822754","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":"Q1899162$760ADBDE-D8FE-4181-87A8-1EB68712428D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Subsemigroups and complexity via the presentation lemma","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Subsemigroups_and_complexity_via_the_presentation_lemma"}}}}}