{"entities":{"Q1062469":{"pageid":1073221,"ns":120,"title":"Item:Q1062469","lastrevid":66061590,"modified":"2026-04-12T07:16:36Z","type":"item","id":"Q1062469","labels":{"en":{"language":"en","value":"Fast language acceptance by shrinking cellular automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3913714"}},"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":"Q1062469$48BDF3B5-D362-4883-9B6B-CB510A86BDD1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8a95d0878c80936c3afc635582c59ea3522a216d","datavalue":{"value":{"text":"Fast language acceptance by shrinking cellular automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062469$DCF72B57-F8DF-46F8-879E-B479E7C69371","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d242121fc3dd755e690b74c88f2289ccce2a2ac","datavalue":{"value":"0572.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062469$AAAF32C9-8316-470D-82FE-B57E9A7A85D3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e0013af5ab73f2d134a6e9810f37087e3bda0dd5","datavalue":{"value":"10.1016/0020-0255(83)90045-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062469$27F5D894-04CB-40B4-A277-8A7C915E39F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dbb0bb61fd4ba583de17475c69948d5f07153e52","datavalue":{"value":{"entity-type":"item","numeric-id":202592,"id":"Q202592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062469$81FB0BAE-A6D4-4CE4-8B5F-3B64FD44384F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ccc368fb0fec453060f9bebad93d2f03150debe3","datavalue":{"value":{"entity-type":"item","numeric-id":472474,"id":"Q472474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062469$1C651604-3070-48FB-9B29-8181104D6024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"15a1c6a9a59e04ce8e75767e3c13585de4c16876","datavalue":{"value":{"entity-type":"item","numeric-id":1062468,"id":"Q1062468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062469$152587A1-B187-4B1D-9F8A-05833A718122","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062469$6E29F0F0-D94B-46ED-98AC-2D9EDA5E5176","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q1062469$ABE283DD-ADD3-4FC9-B78E-D40635BE6C88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f8b2188f165b0b13f22403f20cd67bbc3c55a2f5","datavalue":{"value":"When bounded cellular automata are used as acceptors for formal languages, the number of time steps required to accept a string \\(\\sigma\\) is at least \\(| \\sigma |\\), except in certain trivial cases, since the distinguished cell's state after t steps cannot depend on the initial states of the cells at distances \\(>t\\) from it. However, if the automaton is allowed to shrink (i.e., cells are deleted, and their predecessors become directly connected to their successors), language acceptance in less than linear time becomes possible.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062469$1445E4EC-2DD5-460F-956C-B2D4848CD0AC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062469$8C8D9FA3-ECA3-40EB-B3D9-3E5EE9C9DED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062469$31935E44-9267-4D43-A79C-682E4DFB2E5D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"159c2aec2f0abd3e08d5c10225556cf2bafe8cc2","datavalue":{"value":"3913714","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062469$350DD3E6-8B55-4BB4-9861-C2E4B7585BA7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf773b0649a3b9a99bfcdc415941463141a5f985","datavalue":{"value":"bounded cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062469$CE747125-3B2D-4FF6-B501-B98B694CF1B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6990bbb9121f9767a124ece35e9258ffbeb11c6","datavalue":{"value":"acceptors for formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062469$6722C8D2-C544-49EA-8719-5FA5496AB59D","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":"Q1062469$36A013E7-C6EB-4847-BF07-85A9B2680CF7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"368e61eb6c2253d6706039607322dc6e9fe19585","datavalue":{"value":"https://doi.org/10.1016/0020-0255(83)90045-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1062469$575F713D-D32C-4BCD-99C9-0A127386D40C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ed2e6d4a67e68ed6e27e74df3d3aa55a1ca35a8c","datavalue":{"value":"W2073716439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062469$B689EABC-AD08-4B9C-8121-D727B94D3A56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4d00f377e2761953dfa1ad2164800fbd0161051","datavalue":{"value":{"entity-type":"item","numeric-id":2563020,"id":"Q2563020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062469$F49C1AA8-F7C2-4427-8860-2DC3F9704104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b663e629108a1acaf452be025438df249618ee3","datavalue":{"value":{"entity-type":"item","numeric-id":5677082,"id":"Q5677082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062469$DA6B297C-0145-4BDC-BD93-C5052E015BCF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1959bfdade51658fe70f46da4022fa39010c92df","datavalue":{"value":{"entity-type":"item","numeric-id":1075053,"id":"Q1075053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd7424c9b77b3c576fee32f839cd6a52685bf2b5","datavalue":{"value":{"amount":"+0.8338801860809326","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":"Q1062469$74FCEF16-CF84-4582-A2C3-BDB5476E3BD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70fdaa71b5d205efb8d06447b35410758e3af3c5","datavalue":{"value":{"entity-type":"item","numeric-id":5500619,"id":"Q5500619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"968bae1b4565acc71ba5c5a4da1e1c726ee2d9cd","datavalue":{"value":{"amount":"+0.8277825713157654","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":"Q1062469$4345FEC0-CCFF-49D1-A36B-59F8866E1456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b9f13cba21f259673f7005e35c998233877b4b5","datavalue":{"value":{"entity-type":"item","numeric-id":4837658,"id":"Q4837658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35e06387f3290dcd1408621e8de17e29e441e5a5","datavalue":{"value":{"amount":"+0.7772082090377808","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":"Q1062469$7959E90D-302B-433D-8C8B-C731D85C675F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22229224ac5744dbbb01346a4619fe9d23281f0f","datavalue":{"value":{"entity-type":"item","numeric-id":2640353,"id":"Q2640353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2d7b0270560c4139ac73837f0501f448f6e5896","datavalue":{"value":{"amount":"+0.7771571278572083","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":"Q1062469$4CF2245C-393E-4D9D-AAAE-34451576C3E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f0f15ba3a290ba36a0175dd9ab9e07df1eb1deb","datavalue":{"value":{"entity-type":"item","numeric-id":5041265,"id":"Q5041265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88b395fae08747ab1c88dbb7ca248caf64e732fa","datavalue":{"value":{"amount":"+0.7757356762886047","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":"Q1062469$3CC322F7-D4D3-40A6-A1F0-DBA8BFCADE03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fast language acceptance by shrinking cellular automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fast_language_acceptance_by_shrinking_cellular_automata"}}}}}