{"entities":{"Q343476":{"pageid":345243,"ns":120,"title":"Item:Q343476","lastrevid":61155591,"modified":"2026-04-10T21:31:43Z","type":"item","id":"Q343476","labels":{"en":{"language":"en","value":"Ranks of finite semigroups of one-dimensional cellular automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6656932"}},"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":"Q343476$DA448BB9-BAC3-48CC-BDE9-96AF9BEA3949","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d4efe7fa578528958166951a45e4b5430fde12f","datavalue":{"value":{"text":"Ranks of finite semigroups of one-dimensional cellular automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q343476$B1DDFA8F-8EA0-4AC6-BAA1-3F92E9A41204","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2f2f0861b30826155f84c98740f1dbf13f5d307","datavalue":{"value":"1378.20062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343476$C47263CC-4246-4E26-BA7D-8AF7FBB7AA60","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eba5e5070c71540dfba4b9be28ecae76e0d0502a","datavalue":{"value":{"entity-type":"item","numeric-id":343475,"id":"Q343475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$49B6E014-2D80-42A7-8D50-D248F3508A53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae02f81b70f6dc35a2bcea8dde0071b52b42dea2","datavalue":{"value":{"entity-type":"item","numeric-id":266273,"id":"Q266273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$1F9D0046-0FAB-447B-A658-CAF054142CC7","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":"Q343476$525B5119-2DDB-4977-8175-4104994567F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a7b9cf50e041c6fd07872e805ee230d9cf13e544","datavalue":{"value":{"time":"+2016-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q343476$0BD34F0D-2E94-4D94-A03C-6061547E9443","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c7426d85a5043e3001e123d6c7e7387813b03f13","datavalue":{"value":"https://arxiv.org/abs/1510.00197","type":"string"},"datatype":"url"},"type":"statement","id":"Q343476$08A5ACD0-19B4-4608-B0B0-84A586B81149","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c9a355739c431467a2421f4802107f362c4eaa1","datavalue":{"value":"A cellular automaton over a group \\(G\\) and a set \\(A\\) is a mapping \\(A^G\\to A^G\\) which is determined by the action of \\(G\\) on itself by right multiplication within a fixed finite neighborhood. Such cellular automata constitute a semigroup \\(\\mathrm{CA}(G;A)\\) under composition of mappings. When both \\(G\\) and \\(A\\) are finite, which is the case of interest in the paper, \\(\\mathrm{CA}(G;A)\\) is the centralizer of a certain set of transformations of \\(A^G\\). The aim of the paper is to compute the rank, in the sense of the minimum cardinality of a generating set, for the semigroups \\(\\mathrm{CA}(G;A)\\) when \\(G=\\mathbb{Z}_n\\) is a cyclic group. Explicit formulas are established when \\(n\\) is a prime, a power of 2, or a power of 2 times a prime, while lower and upper bounds are given in the general case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q343476$5BE6DF57-9D0A-4615-B413-85A5CC093DD1","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":"Q343476$51F2F7FB-971D-4F07-86F5-7332D351B117","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343476$0F2CFEDE-80E3-41A1-9C4C-5A596ABDE8DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"28c26f343d909e4a66e25387c3adc02e650c67e8","datavalue":{"value":"20M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343476$5D0E2186-8749-4456-9A80-C76CE415FC39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343476$E2300BDB-7BF9-445E-AE94-87339417E1FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343476$A50EDAB9-6818-4A73-8F75-D8D41A4A35F2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"28c5b6b995eeea8f8efb4dc010e7caecb0357c3b","datavalue":{"value":"6656932","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343476$3C735883-F3B4-464A-9FE5-F48A02F2474B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc4b5d63289db850b148e760ad6fea530c4e5631","datavalue":{"value":"cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q343476$A90E8787-5092-4E08-9BD5-F9E718B49C0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f531b0e0a828fa7a37e8a4a90f6c1f6ca89420f2","datavalue":{"value":"finite semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q343476$5CB58EFE-D9DE-4C11-8142-628331DCB502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5176fe7f59cfd764a3ba2cdb070f3a1f323d6ff","datavalue":{"value":"smallest generating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q343476$C5FB1DB6-76AC-457B-A218-9A408C5CE570","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":"Q343476$99532048-F080-4B14-93E6-30CFCA806F38","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b22e498d28702c26988fe8a4dc1806f09aafd451","datavalue":{"value":"W3104722361","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343476$D79BF34E-B6E6-4526-9A84-174881390A7C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a6f34be3e9935b0f2c05d806c9880ae22988cd99","datavalue":{"value":"Q59474219","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343476$C7FB4C80-A87C-4540-BE16-581F386B0BD1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"939e33ea140ccc320b53ff3561381f58046aac21","datavalue":{"value":{"entity-type":"item","numeric-id":2391158,"id":"Q2391158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$09EC6352-1441-4163-B924-75977B9037D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a95a7c342babc5becaa30e990fa8980cfba942cc","datavalue":{"value":{"entity-type":"item","numeric-id":5360343,"id":"Q5360343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$B0E89143-023E-4032-9B18-3C587A104EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6948ebfeed0edd11f7ffb01b24b2c5a092b66890","datavalue":{"value":{"entity-type":"item","numeric-id":845292,"id":"Q845292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$E9794FD2-F3FE-41B1-8428-3093E9E53A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4363adb8fe36d099e1faf3d99505e099a03ceb4d","datavalue":{"value":{"entity-type":"item","numeric-id":3583434,"id":"Q3583434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$F0EED0AD-1D8E-41A1-8793-11BCB77D76BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4b1461c135729d1b927c71de8e889ef11ebb57e","datavalue":{"value":{"entity-type":"item","numeric-id":1288652,"id":"Q1288652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$47CD2839-BAE4-46FF-A1E6-D2F72B947D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"644beee13e04c9a4d84b983b0ef27c2097dbc8eb","datavalue":{"value":{"entity-type":"item","numeric-id":4882944,"id":"Q4882944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$C73D8D98-0325-40DA-8AAD-0746F83EA3EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd36278a178099e9b82a1ad4e67f41cbbb2a6132","datavalue":{"value":{"entity-type":"item","numeric-id":929383,"id":"Q929383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$9C8E70D5-7F85-45F4-8DAC-746E447424E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff6a0b55791d38d0d4ab05d931d44c425191a458","datavalue":{"value":{"entity-type":"item","numeric-id":3759049,"id":"Q3759049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$FF4CA7ED-BC16-4511-B22F-3EC4E87F912B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ecd3eaa910db638c20fca37dfa4bd34df2f9080","datavalue":{"value":{"entity-type":"item","numeric-id":467521,"id":"Q467521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$7D2B70D1-D461-43B9-8B3C-A6EE990B4A98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce1d279dc5c19122cfcab70617fac23fe7cefa34","datavalue":{"value":{"entity-type":"item","numeric-id":4911055,"id":"Q4911055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$3AF858AB-BBF1-4FA0-9942-E1D59EA5DBF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9f9f4e1361dc0536562bc76183cb5cde3e9caed","datavalue":{"value":{"entity-type":"item","numeric-id":3483478,"id":"Q3483478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$6DBAFF8D-70B6-4078-9893-A952F309AB00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f9ad0314412efec50be5bc0ca0f1365f58142fb","datavalue":{"value":{"entity-type":"item","numeric-id":1779295,"id":"Q1779295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$616AB43C-B3C1-48F7-A70B-9877B01B2C7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46c4cb31835ce023650a9548f74ae3f1dd1ba4ef","datavalue":{"value":{"entity-type":"item","numeric-id":3996618,"id":"Q3996618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$174897FD-726E-4769-83E1-C29345918475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16e74280b45af5c10f96739fe30369511b8d7097","datavalue":{"value":{"entity-type":"item","numeric-id":797582,"id":"Q797582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$242E5DF9-A5FF-4BE6-9703-E50776AEA9FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e45b7e84f554bf195573876811fb02a524c99e02","datavalue":{"value":{"entity-type":"item","numeric-id":5831368,"id":"Q5831368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$B5248156-7A31-4552-BF12-9AA2498C704C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"069453333053b37e591f19d07de0aa3ebcc3ddc9","datavalue":{"value":{"entity-type":"item","numeric-id":5500610,"id":"Q5500610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$1CE0D709-2AE4-421D-A5FA-3C6AC18C9E73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcdc95f618667ad2cc6eef9ec3b6eb6bf972529f","datavalue":{"value":{"entity-type":"item","numeric-id":1072705,"id":"Q1072705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$434ADC18-549D-4E5E-9389-5491AAE35354","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2b5d99ac58ee1b3ed5de2308e05c6a705de7f4a0","datavalue":{"value":"10.1007/S00233-016-9783-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343476$341E1B16-BF4C-4153-A291-B4487B9B1ADA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b58b13cb310417cc4433ec62048bf75daec3c051","datavalue":{"value":{"entity-type":"item","numeric-id":3186476,"id":"Q3186476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c208048621854c39822d27948aa24e68e9e0534f","datavalue":{"value":{"amount":"+0.7819862961769104","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":"Q343476$3238FEFE-7EBD-4026-9165-E3117D453A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01c2eeb84f430475c680339af418ff1bcc9684a3","datavalue":{"value":{"entity-type":"item","numeric-id":2278567,"id":"Q2278567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0cc0b86f9e81c58994353085467c0a3ee6ca9d8","datavalue":{"value":{"amount":"+0.7805599570274353","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":"Q343476$EB072A99-6EF3-40F3-9196-CAC7525E9D33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36d270f16253cb90e6f09277549f90cd93d5e44c","datavalue":{"value":{"entity-type":"item","numeric-id":4911055,"id":"Q4911055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1034e84969f3309fb5ba544184a1b34572a23e02","datavalue":{"value":{"amount":"+0.7805266976356506","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":"Q343476$06ED567D-CC9F-4CCA-B67E-6715CD1CE947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8c858eee0330450596b45c3cfd535a7fa0668b6","datavalue":{"value":{"entity-type":"item","numeric-id":5500610,"id":"Q5500610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c2ed6b356127d0687191292067dc0a2fc49f70d","datavalue":{"value":{"amount":"+0.773276686668396","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":"Q343476$7D226DE6-3B9F-4552-98A8-126E86798865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"022c7a7fcdf1349cf82848095e39d38757c0a1e1","datavalue":{"value":{"entity-type":"item","numeric-id":3583434,"id":"Q3583434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57b4cc56e96dc25e774a36bda3458bd9f2fd1b87","datavalue":{"value":{"amount":"+0.7586559057235718","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":"Q343476$87C62428-AB15-45AD-8046-37E896F98A8D","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343476$3168A25C-9565-4118-BF61-CFEB541AD5F4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Ranks of finite semigroups of one-dimensional cellular automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Ranks_of_finite_semigroups_of_one-dimensional_cellular_automata"}}}}}