{"entities":{"Q1402910":{"pageid":1413650,"ns":120,"title":"Item:Q1402910","lastrevid":70341435,"modified":"2026-04-13T14:07:53Z","type":"item","id":"Q1402910","labels":{"en":{"language":"en","value":"A polynomial time algorithm to compute the Abelian kernel of a finite monoid"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1972514"}},"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":"Q1402910$0081EDC7-20D6-44E6-91AF-A1D019E96EAA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1fe747d354e36b566ddf23f80e4a52d30b25fbbe","datavalue":{"value":{"text":"A polynomial time algorithm to compute the Abelian kernel of a finite monoid","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1402910$D14415BD-DFFA-4356-8CA1-3CBB2EFD3C3E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e215720fd92e8fd788a0da67ac57eff88a190dcb","datavalue":{"value":"1029.20030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402910$8944ABFB-DEC2-4FE4-A6AD-774431315A35","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f350c55bf900503ddaf5352c79dc47de64af0fb5","datavalue":{"value":{"entity-type":"item","numeric-id":372059,"id":"Q372059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402910$BC8C62EC-27B7-4866-8F13-DF3654D111BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b28ad9b4a7f5de9582a5c2b602f54e86b0569ebf","datavalue":{"value":{"entity-type":"item","numeric-id":442145,"id":"Q442145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402910$638EF278-F671-4895-8E69-0AD7874EE2E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"28dbf90a09492d81530507fd711b9336815e58a3","datavalue":{"value":{"entity-type":"item","numeric-id":172569,"id":"Q172569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402910$64EC790B-198E-4988-A8AB-EB67CBEBA135","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cba42c15b60f86e885dacaa10fdf6728507ff845","datavalue":{"value":{"time":"+2003-08-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1402910$A9187C44-C7D9-4C51-A5A3-F28D28BC8FBC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fa7eddfc10b59dacc6e7bbbc7205ff294cae4799","datavalue":{"value":"The Abelian kernel of a finite monoid \\(M\\) is the intersection of all \\(\\tau^{-1}(1)\\) where \\(\\tau\\) is a relational morphism from \\(M\\) into a finite Abelian group. The first author had previously presented an algorithm to compute the Abelian kernel [Semigroup Forum 56, No. 3, 339-361 (1998; Zbl 0909.20050)], but its complexity is exponential in both the size \\(m\\) of the monoid and a given number \\(k\\) for a set of generators. In the present paper an improved algorithm is presented which for fixed \\(k\\) is polynomial in~\\(m\\), although with a large exponent even for small~\\(k\\). The algorithm to detect if an element \\(x\\) of~\\(M\\) lies in the Abelian kernel searches for short paths from \\(1\\) to~\\(x\\) in the Cayley graph of~\\(M\\) with respect to the given \\(k\\) generators whose label is zero in the free Abelian group.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402910$0C0AA97B-2C4C-42BB-B29A-D1E5866C923D","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":"Q1402910$59A8A5CD-3A8C-4FDA-A6BD-44E35FAD2575","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5fb4697c93e6483e0ffbb93428a373e0646b68d","datavalue":{"value":"20M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402910$DD5D80CC-4359-48E1-9FFB-2954CCCCE4E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402910$122D38F4-4C49-4EDE-BD4D-96FC2756EEE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402910$C213B743-0C81-4D50-B74C-F35096641502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402910$7EDDBE37-0D54-4851-A5FB-56D9D846923B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"28371bf660a842a5bb672c10a9cd698350b5eb6f","datavalue":{"value":"1972514","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402910$F26F86A9-C892-4280-B8EB-77ACE2927513","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cc0cd31d36f0ac6a1e4cbb2ecda440630586e55","datavalue":{"value":"finite monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402910$4D0D7A9A-299F-4E48-AA64-026BA35DC878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9db4eff65f85faebf8411107ce9861f94744fb08","datavalue":{"value":"pseudovarieties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402910$555775C9-66B8-4017-87E4-7B39B10C253C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de99e7f702b6736310c9f87d01eb639db75a4c72","datavalue":{"value":"finite groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402910$FCAC3AE9-910A-4672-B655-780F0BE4C3C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34692fa71c3435bcc8312badf5375e1463b7e1f8","datavalue":{"value":"Abelian group kernel","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402910$45A1F459-D79C-45C7-8975-4674EE2A22F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f04f182ece06ea1be9cf6b09d1eeafa2bfa0a28","datavalue":{"value":"free Abelian groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402910$626B497C-C24F-49FF-9AAB-2E8E5F6D4837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b63bb3bdbe19e7ca00b7904e6e96afe6d8cfc258","datavalue":{"value":"profinite topology","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402910$6CDD560F-FC56-4A5B-90D0-008A63043460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402910$BAB37D4F-386D-4C0D-95B5-5F237C43C879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64e1ee688b6f898d32c9c2776a1d825855a56d60","datavalue":{"value":"Cayley graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402910$B7D9AB3C-6534-40B2-8C01-98EBB5F1A100","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"dd7f0abef058f8eae97be2e317c30210cbb29e90","datavalue":{"value":{"entity-type":"item","numeric-id":13081,"id":"Q13081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402910$38D663A7-A1F4-4428-BCD6-50F6CE5851CE","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":"Q1402910$6523A6C0-064C-4FA6-AC8F-EAF8C8BA43B5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d5de8667c540b290968186429e6fe8991c289b0a","datavalue":{"value":"https://doi.org/10.1007/s00233-002-0004-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1402910$2BD8E185-E811-4907-BF76-75F1BFDFA018","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9c6fc167aa3c0a7b66ddac677c4074b5c75fc92b","datavalue":{"value":"W2081347469","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402910$B2BDF56D-CAD4-4CAC-94E8-10C346BAB45C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"685f1a97e7f5535b1303b8a42749fff1d5218323","datavalue":{"value":"10.1007/S00233-002-0004-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402910$8A034DCE-D565-43B2-B135-AFA3A5C51602","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b8d53830f7841730d37f60d57ff8f5d745c9cc3","datavalue":{"value":{"entity-type":"item","numeric-id":2509275,"id":"Q2509275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cc520aea49e81ef3bf2f6ae40fb213e4b78efe4","datavalue":{"value":{"amount":"+0.9288831","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$4DC2C441-359B-4FDF-9AB3-A71870FA777B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a5a438f862c48856cc4c369ff181374be4f203c","datavalue":{"value":{"entity-type":"item","numeric-id":3552220,"id":"Q3552220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3690075714bf00d48238e3b1846a02f8c2c675c","datavalue":{"value":{"amount":"+0.88691074","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$C5A6AAE6-2380-4607-B1E0-BEBBEEA4CA11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb8bfb9e8257d3de6b77467a564e83cd9c46cc55","datavalue":{"value":{"entity-type":"item","numeric-id":4891845,"id":"Q4891845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a7995531d17edb12b81e2792532e7d3a63e3f0c","datavalue":{"value":{"amount":"+0.88568944","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$64EE6513-E75C-4FE5-A058-07991580D29A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c00e4198a57aab203e2a37e310ac8b6f76b2054","datavalue":{"value":{"entity-type":"item","numeric-id":2088733,"id":"Q2088733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22e5aa68784cc98cbad7794a502a01f54e81bc1a","datavalue":{"value":{"amount":"+0.8812566","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$A0352A99-418D-4FD1-874D-B8F4ABF8976F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e76bc8f39987e4ba8b3d54e3090ebcc42d5ec4e","datavalue":{"value":{"entity-type":"item","numeric-id":4370002,"id":"Q4370002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"068f9c93333cff3dd367fbfd781fa5e802ffcede","datavalue":{"value":{"amount":"+0.8766073","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$0B900464-3E4E-4295-8B55-9959E31748DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adb529227670c4373f6f105d5af2778c4fc52b5b","datavalue":{"value":{"entity-type":"item","numeric-id":1358921,"id":"Q1358921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b00329efdfee1eedfa895a064fcdb6e4d8275088","datavalue":{"value":{"amount":"+0.87420046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$86FA93A8-5B95-4F0B-AA9B-3F0701ED5DF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7494e846fc0941922c58fcb2e39d4a285b01668","datavalue":{"value":{"entity-type":"item","numeric-id":4226940,"id":"Q4226940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d975552bc7b4b4f80061137657c8688e4d8b113","datavalue":{"value":{"amount":"+0.86905015","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$BAA41CD9-DA02-40CE-855E-A1794D236977","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c477c4d6739c6390584e17116aca2beee38f948","datavalue":{"value":{"entity-type":"item","numeric-id":1192353,"id":"Q1192353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7b81bbdc5d12827a7dea7baf7d9c1441490e4e6","datavalue":{"value":{"amount":"+0.8630735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$5C73477B-D05F-49F8-BD08-A83A70787904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8d6905bb57c32ffd5839ec64632c35791ff3035","datavalue":{"value":{"entity-type":"item","numeric-id":1590072,"id":"Q1590072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fdf77b3b583691fa571872e2194180a69a4705b","datavalue":{"value":{"amount":"+0.8616331","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$9F003664-56B9-4872-B98B-49AF18926144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04df0b52ef402cde049c9c8375edd37a42b47dad","datavalue":{"value":{"entity-type":"item","numeric-id":2643523,"id":"Q2643523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b034bd436826db513ce128bc830a67a3e889956","datavalue":{"value":{"amount":"+0.8596421","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402910$FFECA9E3-5B83-40E6-96C3-237D66A76A90","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial time algorithm to compute the Abelian kernel of a finite monoid","badges":[]}}}}}