{"entities":{"Q1122664":{"pageid":1133413,"ns":120,"title":"Item:Q1122664","lastrevid":66467259,"modified":"2026-04-12T10:16:21Z","type":"item","id":"Q1122664","labels":{"en":{"language":"en","value":"Programs over aperiodic monoids"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4107110"}},"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":"Q1122664$8D4678AB-6B07-4EBA-A02A-7B429FA6CFEB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4510590bff978ce4a6ef849cc41c6dfdebcbe746","datavalue":{"value":{"text":"Programs over aperiodic monoids","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1122664$0BF50A61-2178-46D6-8C6C-06474F0F89FC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6fd9b069f62cc553a1a60e2770a95d1e8a194e30","datavalue":{"value":"0676.20043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122664$DC1A80E2-0B65-456F-A845-1D3B7D64CA3E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6d6ba07fb0c7bd8d3e162b4330af096d3e37c521","datavalue":{"value":"10.1016/0304-3975(89)90051-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122664$12066DFF-C2D9-46FE-9530-6706BD90B58B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5fda2b843008097467141f2c2de99a1b410da08e","datavalue":{"value":{"entity-type":"item","numeric-id":685707,"id":"Q685707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122664$99AA502B-29A4-4A0B-A4F2-510FDE8440E7","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":"Q1122664$18CAE6B1-48BE-4050-8B54-B60229E0AEA3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1122664$045D7B4B-5C85-410E-817D-E4FC75E7F169","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b23024b13f6d2d1fbfa6d612b7c85d84f58ff1a7","datavalue":{"value":"A program P over a finite monoid M is a finite sequence of instructions, i.e. of words over the alphabet \\(I_ n=[[1,n]]\\times M^{\\{0,1\\}}\\) where n is a fixed integer. To each program \\(P=\\iota_ 1...\\iota_ k\\in I^*_ n\\) is associated a function \\(f_ P\\) from \\(\\{0,1\\}^ n\\) into M. This function is defined by the rule:  \\[  \\forall w=w_ 1...w_ n\\in \\{0,1\\}^ n,\\quad f_ P(w)=\\prod^{k}_{i=1}f_ i(w_{k(i)})  \\]  if the i-th instruction is \\(\\iota_ i=(k(i),f_ i)\\) for every i in \\([[1,k]]\\). A language L in \\(\\{0,1\\}^*\\) is then said to be recognizable by M iff for each \\(n\\in {\\mathbb{N}}\\), there exists a program \\(P(n)\\in I^*_ n\\) and a subset \\(F_ n\\subset M\\) such that \\(L\\cap \\{0,1\\}^ n=f^{-1}_{P(n)}(F_ n)\\). It is to be noticed that a language recognizable in the usual sense [cf. \\textit{J. E. Pin}, Vari\u00e9t\u00e9s de langages formels (Masson, Paris, 1984; Zbl 0636.68093)] is also recognizable in the sense of the paper, but the converse is false.    The paper presents first a specific aperiodic monoid U which is universal in the following sense: any language L over \\(\\{0,1\\}\\) can be recognized by U. Secondly, the author studies different classes of non universal monoids. More precisely, it is shown - modulo some technical precisions - that every monoid M in the semigroup varieties \\(R\\vee L\\), DA or \\(J_ 1*G_ q\\) cannot recognize the language \\(MOD_ p=\\{w\\in \\{0,1\\}^*\\), \\(| w|_ 1\\equiv 0 [p]\\}\\). Finally, the author conjectures that an aperiodic monoid M recognizes \\(MOD_ p\\) iff U divides M.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$F37F16A7-8E2B-4771-A5FD-D64A7DE6C970","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122664$F9847258-A192-44DF-A24A-BC03D4E6F463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5fb4697c93e6483e0ffbb93428a373e0646b68d","datavalue":{"value":"20M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122664$424F4064-1D35-4872-BA64-DDEB37242342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122664$3077378F-8FE7-4476-B96C-158724F2A8C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122664$6F2C7D46-A2C0-401B-BEA8-857C4B3A4056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122664$481D2F98-0204-424D-8568-2241F7E29DB9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1006eed045a7fb5e3f4365a3388c4986c08d7926","datavalue":{"value":"4107110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122664$0503FEBA-9E1C-447F-B498-22425C79D196","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe708dcce91d571d1ebd3853007f0b16521f4c8a","datavalue":{"value":"Boolean circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$DEB55ED8-B77E-4A98-9A5C-A41D87B4FB7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e0a28a0e3afea9dd009004a4e84d68686b1e56a","datavalue":{"value":"counting modulo p","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$272C28BA-7548-4E63-8E87-D7B925C41CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$95C6255D-C3B0-4208-850E-77088FF327FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecde1dfa99d1cbd08aec8d0026129ef8a157b8d6","datavalue":{"value":"recognizable languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$83EEE2B9-EC3E-4D94-AC84-D3A965528A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123212aa79a8c6aa156264be1012ed5853d996c","datavalue":{"value":"program","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$CCCAC949-060C-43BB-979E-C2CA0467D3E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013ea0ae18b29892b5726356388c7d5d42063956","datavalue":{"value":"finite monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$3ADF85C7-B0EF-4BFB-8398-3FB42D43012B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b99d5dcd36ca4f6ddee80af79486b0b82119f69","datavalue":{"value":"words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$52E10F9D-D363-4860-B196-6A65F323237F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b06f809e2a2d49d26b8d7de0f8648aa58d470d7","datavalue":{"value":"alphabet","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$94AB71CB-AA52-46EF-9BED-17113642EE31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e530128c35e1484ef9d13700b8e4e9929cc989e","datavalue":{"value":"aperiodic monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$F09E2003-C535-4EBC-8D83-B851C6445816","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d274cca3cde8d8dadd42c2bd50ebfaa927d71f15","datavalue":{"value":"universal monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$7580F759-1CDD-4555-8610-6F13387E474D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77aa39a453056bf57cb855f01b7554092a313eab","datavalue":{"value":"semigroup varieties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122664$819D0F56-4E36-4862-A600-AE4A657589FC","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":"Q1122664$035FA942-F2F0-4CB3-9FCD-0AB7C91EABCE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1dcd27d09de0f3ca8442635e3a6ba14e64476cef","datavalue":{"value":"https://doi.org/10.1016/0304-3975(89)90051-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1122664$C628A326-7677-4846-B327-ED24F6821E71","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f8241c7aba8390cc80c63e44bb8e8ab34c9bfe59","datavalue":{"value":"W2058707009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122664$6BE002AA-FF25-443F-9A08-DE73FA9F25C5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2299871f8da3ff873a8d3556c58e2f6c60e4e2b9","datavalue":{"value":{"entity-type":"item","numeric-id":1242697,"id":"Q1242697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122664$10D13EA8-9F2E-4310-AE08-CEC55F3596AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ee19e43fe0ba6119b46095472780b34cb314009","datavalue":{"value":{"entity-type":"item","numeric-id":3773353,"id":"Q3773353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122664$2AA78266-46ED-420A-9789-A18F1FB25A42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122664$210DE7E4-ABCE-4AD9-B5EA-87D92266392B","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":"Q1122664$B4A3F4AC-3A40-4B42-B14E-26942F3346FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70149cae8f99255f0ad252fb21c7901c2462fe82","datavalue":{"value":{"entity-type":"item","numeric-id":3776657,"id":"Q3776657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122664$997C3003-6C86-42F0-BB8D-877B731AA861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6a75e85707c1f24d3c13217ffc94cef40ecf304","datavalue":{"value":{"entity-type":"item","numeric-id":1244582,"id":"Q1244582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122664$EB7787AE-1BBF-4A0C-9F86-1CD8A753308C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c7bb4df12fd3bd722543714aeaf7b7bf2fdef42","datavalue":{"value":{"entity-type":"item","numeric-id":1118041,"id":"Q1118041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f12967756bd6ecb87d560049161838c71425f93","datavalue":{"value":{"amount":"+0.8648543357849121","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":"Q1122664$03969225-7C6F-4673-A19A-3019A91192A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"501eb88dc72e18f4db36759fa83a6704263e148e","datavalue":{"value":{"entity-type":"item","numeric-id":782588,"id":"Q782588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8be0080ccf070b8f45099832d8dc5c4aa4167a00","datavalue":{"value":{"amount":"+0.8082796335220337","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":"Q1122664$10EC828F-27E6-4C85-BA32-9C6268A6BB0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30eb5144e45818a7b980c053b4c60f6d4b027612","datavalue":{"value":{"entity-type":"item","numeric-id":5111216,"id":"Q5111216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d1b35a9341ae0557e7305ea9bc336e3241651ad","datavalue":{"value":{"amount":"+0.8003429770469666","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":"Q1122664$E875FF75-4AF4-4575-B601-4398F148CEEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"253882b99b7f9adfd67e3307aee1e448b4566191","datavalue":{"value":{"entity-type":"item","numeric-id":3779765,"id":"Q3779765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7024658933d4e45cb0a13d7d9bcb106e1d29032b","datavalue":{"value":{"amount":"+0.7883331775665283","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":"Q1122664$78AA6627-D7C2-4DB3-9EDE-974CD5D7FF4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2aaa0e4720e6a7d4fa3129e083e5ec348d6c34fe","datavalue":{"value":{"entity-type":"item","numeric-id":4807833,"id":"Q4807833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f669c2541f3200975fa50eedefcd1a9db41921c","datavalue":{"value":{"amount":"+0.7826260328292847","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":"Q1122664$61DC25B5-161D-45D7-8564-9AC71E044D37","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Programs over aperiodic monoids","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Programs_over_aperiodic_monoids"}}}}}