{"entities":{"Q6549671":{"pageid":14160825,"ns":120,"title":"Item:Q6549671","lastrevid":55675978,"modified":"2026-02-17T20:49:41Z","type":"item","id":"Q6549671","labels":{"en":{"language":"en","value":"Simulation limitations of affine cellular automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7859409"}},"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":"Q6549671$9FEE1356-EBA8-4543-A640-9199D7CBA5C8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7e13737b19a47470e8820ce4094d8544dc4bb9e3","datavalue":{"value":{"text":"Simulation limitations of affine cellular automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6549671$FA0D9FD1-1139-4FC5-9239-D7AEC0879D56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3952d9bdefd950840ff04a398edcb23b39ac5f5","datavalue":{"value":{"entity-type":"item","numeric-id":6549670,"id":"Q6549670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$62C887B5-E269-4650-A99B-16D6D92C4636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"15687bfd5df3847de166ba008e270b5167179caa","datavalue":{"value":{"entity-type":"item","numeric-id":2071771,"id":"Q2071771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$0B9FAB6C-16F2-4F8D-86D1-8E1EDC1D1185","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":"Q6549671$DCD44FB5-7843-4A19-BF54-F6D9DEDE225B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e6e97122a60c7ccedaaeb96c6b0234ae8eb3c22d","datavalue":{"value":{"time":"+2024-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6549671$253602AD-E45E-4F43-B7EB-29AFFD714BC7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"55f7c94102f4921257d52d3f72f54560e96d859e","datavalue":{"value":"This paper contributes to the formalization of the computational capacity of cellular automata by developing the notion of simulation (automaton \\(A\\) is said to be simulated by automaton \\(B\\) if each space-time or orbit diagram of \\(A\\) can be reproduced by \\(B\\) up to suitable transformations). The abstract ideas are applied to affine automata, and the main result is that most affine automata over a finite field can only simulate affine automata over the same field. This in particular strengthens known results on limits to the computational capacity of linear automata. More generally the results allow the notion of simulation to be formalized using language from universal algebra. This shows how, for example, some of the results here are consequences of deeper results due to \\textit{J. D. H. Smith} [Mal'cev varieties. Berlin-Heidelberg-New York: Springer-Verlag (1976; Zbl 0344.08002)] and \\textit{H. P. Gumm} [Algebra Univers. 9, 8--34 (1979; Zbl 0414.08002)] about abelian algebras with a Mal'tsev term and provides additional tools and perspectives with which to study the simulation capacity of other classes of automata.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6549671$1EC57D33-3A4B-4EAE-93E0-6D90032421C9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1f527af6021fa2abbecdfd313d9268f87b4cbc0f","datavalue":{"value":{"entity-type":"item","numeric-id":241587,"id":"Q241587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$1A172597-94B5-49D0-ABB9-19208BA2F6DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6549671$2E70BD9B-5717-4738-ADBD-65B8622C5BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"20bb5571a1bc4300de51d23c463eb631840cb343","datavalue":{"value":"08A70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6549671$526AADB0-18EA-43A7-9789-4AC744710293","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f6df8e0112b56b79538f3a40d394a94128584db","datavalue":{"value":"7859409","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6549671$209F782C-427D-4451-B513-2FB9F17B0D96","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc4b5d63289db850b148e760ad6fea530c4e5631","datavalue":{"value":"cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q6549671$48EDC6D8-98B5-4113-9B3D-CA1AE676761B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1587ab521b3c37367b54740e7c94f68ed85061ec","datavalue":{"value":"simulation capacity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6549671$53CA4180-143D-496D-96A9-E01E39BBD888","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49085ec2a42d0302fd73bfcc2920c31adb3434b9","datavalue":{"value":"affine cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q6549671$F1776DE2-0765-458D-BFBD-5CCB6EC1ABAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"845bb3d1cf932f59db9283a6d047b4db2e7c9e17","datavalue":{"value":"grouping","type":"string"},"datatype":"string"},"type":"statement","id":"Q6549671$81599C48-9D13-492D-9651-3C45855390BC","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":"Q6549671$A40A8EC1-3AF7-410F-B737-07C2A41BA60D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9b0b626f185b157a198fc727e2b91261f695dda","datavalue":{"value":{"entity-type":"item","numeric-id":3802629,"id":"Q3802629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$64B34025-F074-4DC1-A28D-F79CCEF7D6EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12675a71519d1459acce3a3c16c5d87ae3312d58","datavalue":{"value":{"entity-type":"item","numeric-id":1917296,"id":"Q1917296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$B2C33447-0861-4E59-AB32-89C10418C572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"400509fe5fb142373707d763108c4fa56265a140","datavalue":{"value":{"entity-type":"item","numeric-id":5321501,"id":"Q5321501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$A5CA132D-0343-4C44-AFF7-740617C33457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b818d4bd7f27fa6c952a88fbe07493f15c21be1c","datavalue":{"value":{"entity-type":"item","numeric-id":549700,"id":"Q549700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$F30940E3-C49E-445E-9FB9-31D8F542A78C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ecd62a27a42f724dbac1c6eaa2b64dd268fc819","datavalue":{"value":{"entity-type":"item","numeric-id":549701,"id":"Q549701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$F88BD5A7-A2EC-47CC-A634-18C774B036A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e4acd66e6671137c998b0fe6aaa4aecc3a8a0d8","datavalue":{"value":{"entity-type":"item","numeric-id":3416092,"id":"Q3416092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$B8B40BC3-86D2-4D18-B69C-5037C0742D13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b9dbf410ce6ab44efaa843ec4b205aea7fa47b4","datavalue":{"value":{"entity-type":"item","numeric-id":5048944,"id":"Q5048944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$18A70003-C897-445A-B153-D9AAC89D3EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"476fc126d9c783210b5b15619ebd1a1d298b8640","datavalue":{"value":{"entity-type":"item","numeric-id":1583597,"id":"Q1583597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$3B9F0A18-E4E7-4BEF-8800-85DA3C87BB7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c99fcc8e820c1cc4ac6c486483d65c4601fa543e","datavalue":{"value":{"entity-type":"item","numeric-id":1235274,"id":"Q1235274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$4677114B-F97F-4B93-8996-79376AAD538C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f02fc78beac2fe37236d89b55a752d2fd8d1cb8","datavalue":{"value":{"entity-type":"item","numeric-id":616488,"id":"Q616488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$8DAA888F-A2EB-4F90-BEDF-CA148C57E979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd6247f210f4a196f57442e86034ea56685575c9","datavalue":{"value":{"entity-type":"item","numeric-id":1099618,"id":"Q1099618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$6D0F0AED-7DB2-4A3E-BB4A-E43AD17F462A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62c5130231c3b6888d8401cfff50e0b32e21a965","datavalue":{"value":{"entity-type":"item","numeric-id":599073,"id":"Q599073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$719C7D37-8BF5-48C9-BDE0-EEE7D6BA9E43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e06a4a5d3a8bc5bc57f5efdedc2dcded4be73a5c","datavalue":{"value":{"entity-type":"item","numeric-id":5966489,"id":"Q5966489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$29625359-E3E9-4C11-8DE8-FEF4B194CE82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f55fa9bf936d8b9c4401f94aae1b087647f7e71","datavalue":{"value":{"entity-type":"item","numeric-id":2776541,"id":"Q2776541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$B5C80665-FDEB-49FF-81A4-2D3C891D26B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e0f79c5f8d6c131861c7bc1f55796cc9bbfa50e","datavalue":{"value":{"entity-type":"item","numeric-id":3212313,"id":"Q3212313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$6DFBF59B-8352-4DCD-957F-CAA524335E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d8cf82e2bbc5dfb787547c6cb2918aad3d00048","datavalue":{"value":{"entity-type":"item","numeric-id":1058294,"id":"Q1058294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$5E3D5F0E-01C0-4397-B223-B884FEA8586A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c79228704b7016f4ef0735b8958e13fccbde0553","datavalue":{"value":{"entity-type":"item","numeric-id":4218158,"id":"Q4218158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$9EFE4FAC-2BDE-4E1B-8CD9-216722A07ADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e44f7968404c540c847652fe4fca0a703e05d10c","datavalue":{"value":{"entity-type":"item","numeric-id":4381385,"id":"Q4381385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$9D0317E2-517C-46BD-93DF-62006CB63396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"708bef4cf54ecda5bb27d731ad4da8c4f5bbd0f6","datavalue":{"value":{"entity-type":"item","numeric-id":4418687,"id":"Q4418687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$30FD84A2-BB1D-40F0-86AC-0702810F7651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5786176363d4fccc6d95a96c938497ab56d101dc","datavalue":{"value":{"entity-type":"item","numeric-id":4737167,"id":"Q4737167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$A5A3BE60-DA32-491E-A594-FE9400AF5CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff02b1fd6475421bb663d640a4538cea72e3e90f","datavalue":{"value":{"entity-type":"item","numeric-id":3394915,"id":"Q3394915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$CE65756B-93E2-4314-AB84-EE60BE0DF1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20f1fe91abc91b2d9ebbff4fd5445b943f49c2e2","datavalue":{"value":{"entity-type":"item","numeric-id":1232428,"id":"Q1232428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$FDBFB06D-AF88-4C36-999A-AE2B0AFF0BDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c18aa1b0017f2998f3167d5fe08e484451e265b","datavalue":{"value":{"entity-type":"item","numeric-id":5710892,"id":"Q5710892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$42688821-7DD0-4D2E-B28F-0C4E702DBCCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29ef5b34874dd34a473cd320d2683b5e5b4bbce6","datavalue":{"value":{"entity-type":"item","numeric-id":1185247,"id":"Q1185247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6549671$130AD42C-65BD-4CE6-9142-B6162AE919E4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d7da9cf7e3ed9753b4737c158379488ddc092754","datavalue":{"value":"10.1016/J.TCS.2024.114606","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6549671$15747899-7693-4B77-9390-6C2E5E49B177","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe9ee687f6147bc4c8b63e76f4dd275659a62280","datavalue":{"value":{"entity-type":"item","numeric-id":5096354,"id":"Q5096354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4966d15bd5bdf26e5dc4c3f45a3c9311d90f56b","datavalue":{"value":{"amount":"+0.761444091796875","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":"Q6549671$14AFC258-2BE0-435C-8D89-A3C0BCDA7AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"378c8187142cbe9862fb3cc142a417833d33b371","datavalue":{"value":{"entity-type":"item","numeric-id":2326807,"id":"Q2326807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"697b3ec889388ee3ec235cd8563ea52769f63f6d","datavalue":{"value":{"amount":"+0.7611417770385742","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":"Q6549671$584A549A-1945-48CF-ACC5-0D33567C7DA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36fd8a7f8a2969d930c2a8629439eeb5da3fb1a9","datavalue":{"value":{"entity-type":"item","numeric-id":3449997,"id":"Q3449997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c538477e1cf19e08363fdab4697ea456af2dad28","datavalue":{"value":{"amount":"+0.7604209184646606","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":"Q6549671$94A32DBA-C453-4D0F-8CC2-5AF4891FC5D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"529383f7a6b9954228f50ff194dea3ac00414823","datavalue":{"value":{"entity-type":"item","numeric-id":5013888,"id":"Q5013888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd919bc99192a597f2b4b4b3ac35f9282ebcff08","datavalue":{"value":{"amount":"+0.7581689953804016","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":"Q6549671$E01F1DB3-6091-446E-A205-D03E52006208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25a454b4cca6eb58b14927eca47585eaaa53a585","datavalue":{"value":{"entity-type":"item","numeric-id":6095491,"id":"Q6095491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14966524339ce8498d1ba4d9affeaadab569bf7d","datavalue":{"value":{"amount":"+0.750585675239563","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":"Q6549671$B919037E-08D6-4105-9E26-FDF89126E018","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6549671","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6549671"}}}}}