{"entities":{"Q2909191":{"pageid":2919916,"ns":120,"title":"Item:Q2909191","lastrevid":42485091,"modified":"2025-06-28T17:33:02Z","type":"item","id":"Q2909191","labels":{"en":{"language":"en","value":"Two-dimensional languages and cellular automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6073939"}},"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":"Q2909191$409BBF39-CD6B-425B-8B06-D44FB13C63DA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3015da07372776dbdb5ad2cf7fd4c866e6636208","datavalue":{"value":"1283.68227","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909191$8C7044A0-4C75-4333-BDB3-463E51BEE4F1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"74fd7cb063952dd56fa9fc48cc3932ddeaa5cef1","datavalue":{"value":"10.1142/S0129054112500037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909191$7660BC3B-B64F-4EA8-9F36-D6EF8277562C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60c5842f155ee8238eeba54a9dc28801f1bc5640","datavalue":{"value":{"entity-type":"item","numeric-id":243837,"id":"Q243837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$52434AD6-1791-49F7-9045-C40266E14BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a56b110bd9872402ba4a7bf1fcb8811597d07b1","datavalue":{"value":{"entity-type":"item","numeric-id":332435,"id":"Q332435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$76B9AFB2-EAB3-47B9-A771-BD1A0A4E3FB9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"47adaa7123c6f3744cf7fa8eab088d52b4982295","datavalue":{"value":{"entity-type":"item","numeric-id":2703009,"id":"Q2703009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$60B7B4CB-44C0-4D2B-9C0B-1E0F4A33F23D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9ea979e1010c32afb4768abd2ba95f7b0dc31ec2","datavalue":{"value":{"time":"+2012-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2909191$36AC5CB6-7EAC-4DF1-A0AA-F4A672F7249D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909191$FB23915B-5FE3-4641-8E01-2695AC8D3B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e9f75a1ea6a1b050032188834d6ec5de5f473dd3","datavalue":{"value":"37B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909191$0AFBB582-6618-4E37-B432-AA7BFD8CCF58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b559307b5b2969939e6945d65ee127220f8f6f4b","datavalue":{"value":"37B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909191$122CCF7F-9B60-4972-A253-AF85809133FB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e7b818398dd3624c13a17e5aa74d314b5db3009a","datavalue":{"value":"6073939","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2909191$FD7DDF81-3B81-4BE4-8789-AD666240B307","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc4b5d63289db850b148e760ad6fea530c4e5631","datavalue":{"value":"cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909191$32F49B33-8DB2-48DC-9461-49352A31253B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c4be67f451973daf6ead3eaedb49f1f3589a49e","datavalue":{"value":"picture languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909191$E387DDA9-928E-422E-BC4E-81DD72D08C49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6ce889a8a92a5adf9884f2ba6068fac0f7d64b3","datavalue":{"value":"traces","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909191$06A1A376-8A6B-4BF0-9674-6C40BDD00919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9e247b0bd10a9182cd86269887b5bdf052d6285","datavalue":{"value":"shadowing property","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909191$A350C8A2-DAD6-4DBB-8F1E-E322627C6392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf5dc7a956c268d6dbef50de1ed0bec8966fe5e","datavalue":{"value":"SFT traces","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909191$79C0CCB8-2EFB-4107-8260-B0F283939944","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":"Q2909191$867F95D9-8E0C-4F00-8ABC-8CB2B5E5F859","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"470a5434dce95dd9329850607a3e8fa19c968ac2","datavalue":{"value":{"entity-type":"item","numeric-id":671375,"id":"Q671375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$7543249A-85E7-4C55-9BF4-4EA11C135327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9700989d35ed983bcafbf14c6242af25e2d0c094","datavalue":{"value":{"entity-type":"item","numeric-id":1704105,"id":"Q1704105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$5D7CB267-7DF0-475F-9F2A-4390B0E22015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b5b532d3227f7e1f55651fa04b0ef8494e4d20b","datavalue":{"value":{"entity-type":"item","numeric-id":3602813,"id":"Q3602813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$885F68DD-EF58-47CB-A74E-D9FE4B9C5602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a312e4457ce24823d78a6c0f467639d9459cf475","datavalue":{"value":{"entity-type":"item","numeric-id":5958128,"id":"Q5958128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$FC51BBA9-0FD7-4496-91D0-6D4F7DB392C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03c45906f075d58855a2376ea03d0c4ba062c00e","datavalue":{"value":{"entity-type":"item","numeric-id":4016914,"id":"Q4016914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$5B10FED4-6226-41CE-AAFC-253CEDED6127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea132d317dcdbef3507645010bd4498eaf6044d2","datavalue":{"value":{"entity-type":"item","numeric-id":4337811,"id":"Q4337811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$96F06F3A-483B-4496-A8D3-F027A9777847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93c253900e4829cb5d0d6d60e214b68399dc4e6c","datavalue":{"value":{"entity-type":"item","numeric-id":4856597,"id":"Q4856597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2909191$BD5CB3F9-20ED-4EF3-A004-C447F8FD3122","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4edf8a17f83aa5f960891e77e3023c7210e9666a","datavalue":{"value":{"entity-type":"item","numeric-id":5396373,"id":"Q5396373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4acb6c3abec7ee7af67f5beb1b6a555247555de","datavalue":{"value":{"amount":"+0.8282764","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$8CAC1BE3-BF45-491A-B542-8ECB884F9B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2c1067a75b0db67e059f88ed690ee6cb4f48fb7","datavalue":{"value":{"entity-type":"item","numeric-id":3525579,"id":"Q3525579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6efdbe785f72b21fcf86b1c7d60ceff0f5ac967a","datavalue":{"value":{"amount":"+0.8174182","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$05511B81-FE2E-41A9-86FE-1ADB39C26932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac9c87dc416191e620c003848dc88a023ad6f5f6","datavalue":{"value":{"entity-type":"item","numeric-id":5096907,"id":"Q5096907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b9eb76c9058e10e10aff13efd6cc6dd9c16b611","datavalue":{"value":{"amount":"+0.81586975","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$60BEC54A-1986-4488-96C4-7D77B39EE1DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"929153ff491fcaf6f745fc23a37158f8ebe09d16","datavalue":{"value":{"entity-type":"item","numeric-id":807036,"id":"Q807036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f38d86f8d7dbab5dd4ce77d8315b82b15cd393ea","datavalue":{"value":{"amount":"+0.8156693","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$E7AC7A63-F2C3-4069-86F2-5DD2C7473D37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff7c091a77f473b7fda5dbfff492f1f521079591","datavalue":{"value":{"entity-type":"item","numeric-id":2869780,"id":"Q2869780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"611d456a764aa1bc67f886c2c310e462d306f3cb","datavalue":{"value":{"amount":"+0.8148111","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$B3BF75B6-7FD1-4E8A-8021-80B5C2696EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3841eb813a031dfa9877bf2bca454def1fce8b9f","datavalue":{"value":{"entity-type":"item","numeric-id":3113745,"id":"Q3113745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a36c82b59f2b7b41635ec7eed553d7dc7ed331d","datavalue":{"value":{"amount":"+0.8129643","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$B2106E2E-73CB-4DD4-A53C-71DE31D26018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e5f5374d615d29787b78b57f4fd48b5ed4c1962","datavalue":{"value":{"entity-type":"item","numeric-id":5710873,"id":"Q5710873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae912b406ec2e32274e79fb6c157412ea20a55bb","datavalue":{"value":{"amount":"+0.80540156","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$7AED8CF7-826B-43B3-B299-2D379DB6A445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c02e74d3d130c9c82aaa5ebfd9d1fe81a772539f","datavalue":{"value":{"entity-type":"item","numeric-id":5311118,"id":"Q5311118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80a606937a43d2dfa1dfe9dcfc285d547be4153d","datavalue":{"value":{"amount":"+0.79501545","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$440B8401-6389-43E8-9DD5-6DD8D77335F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f5d1327feb1d41cfe5212dfa27f7f0ed61f7756","datavalue":{"value":{"entity-type":"item","numeric-id":3212296,"id":"Q3212296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9618b4ff109d6eb9c350768b0537ab7e8744576e","datavalue":{"value":{"amount":"+0.7947515","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$482D0C7D-973C-4957-93E8-016F5563DB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5786ad3111497a78af97b78af6cda48e6438a30a","datavalue":{"value":{"entity-type":"item","numeric-id":3361900,"id":"Q3361900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fe076f4654634f155cdc7e7ae09bc8b6214ae9f","datavalue":{"value":{"amount":"+0.7923308","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2909191$C0DF568E-BAB6-40FC-BC79-57C132527E71","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e489b53e8c6bf0df910073b92efbe2c53d89bb67","datavalue":{"value":{"text":"Two-dimensional languages and cellular automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2909191$443C99E7-0241-4ACA-9A7B-BDCDCD629758","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"847cfe2f281d9d8a7e8a2e692be8cbc0a716148f","datavalue":{"value":"This article studies cellular automata (CA) through the new point of view of the picture language that they generate, that is, the set of blocks appearing in the half-planes that the evolution of bi-infinite configurations draw (space-time diagrams). The authors define the so-called factorial-local CA, whose language can be defined from a particular (finite) family of allowed blocks of some fixed size.NEWLINENEWLINEThey remark that this fixed size can always be taken to be the diameter, and that this class corresponds to the class of CA whose all (or one) sufficiently large traces (that is, sets of infinite words appearing in columns of the space-time diagrams) are subshifts of finite type. This class was studied in [\\textit{P. Di Lena}, J. Cell. Autom. 2, No. 2, 121--129 (2007; Zbl 1135.68488)]. In particular, it includes nilpotent CA and is included in those having the shadowing property (see [\\textit{P. K\u016frka}, Topological and symbolic dynamics. Cours Sp\u00e9cialis\u00e9s (Paris) 11. Paris: Soci\u00e9t\u00e9 Math\u00e9matique de France (2003; Zbl 1038.37011)]); they give a counter-example to the converse, as well as one factorial-local CA with one trace not of finite type.NEWLINENEWLINEThe main result is the construction of a suitable (complicated) finite automaton that gives the decidability of whether a CA of a given radius corresponds to a given factorial-local language, from which is derived that the property of being factor-local is undecidable -thanks to the above characterization, this appears to be a particular case of [\\textit{P. di Lena}, in: Proc. of the 4th IFIP Int. Conf. on Theor, Comput. Sci., 185--196 (2006)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2909191$60A258BC-1DD4-4C58-9199-355EA452B313","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2909191","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2909191"}}}}}