{"entities":{"Q2805444":{"pageid":2816182,"ns":120,"title":"Item:Q2805444","lastrevid":52527794,"modified":"2026-01-22T21:23:43Z","type":"item","id":"Q2805444","labels":{"en":{"language":"en","value":"Finite automata with multiset memory: a new characterization of Chomsky hierarchy"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6579358"}},"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":"Q2805444$40210C81-B93E-4697-BAC2-407D7413204E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2b74f4cb8505a9f6464aeb120ba480012bb6059","datavalue":{"value":"1342.68187","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805444$45323BFF-AC7C-4684-85C8-1B3C91F0C5CC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0a0a29078b4258b2fcc0e2201a2a119b573147e9","datavalue":{"value":"10.3233/FI-2015-1196","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805444$42F998C1-CFA6-40AE-85B2-38AF3114F04A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"256f1cc5a51015351602e6ffd9fa9c68e40eeabe","datavalue":{"value":{"entity-type":"item","numeric-id":418798,"id":"Q418798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2805444$75B84EE6-326D-4926-94B7-C566881605FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"728153b93b3ca6d18b5006016cbd1877ac7635c0","datavalue":{"value":{"entity-type":"item","numeric-id":243844,"id":"Q243844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2805444$36B03957-24C5-451F-B5A3-39BFB6AF5313","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1529db038bde6a8aed76ac5e8432917aee1a9200","datavalue":{"value":{"entity-type":"item","numeric-id":2803574,"id":"Q2803574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2805444$07277D30-888F-48F8-9B99-E78EB1E42B1A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"39aa9fdf5ab62c801ce885c7d8f139e97b3cfa9f","datavalue":{"value":{"time":"+2016-05-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2805444$9670D641-9422-4D73-86B3-268C21F96753","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805444$25215D00-9E2C-42BC-A9A8-8EE4401DFECF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d1daf66e413feb2b331dff594daf1052f386ca45","datavalue":{"value":"6579358","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805444$19AC09DB-4CCC-431C-9B66-C0EE25246C16","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805444$F61F51B9-7F7A-4F05-A84A-465D03372D71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"caa60be7f6bc77b0f4685ffe49f8b6c8b1886671","datavalue":{"value":"multiset memory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805444$26F37643-3168-43BF-A8D5-640D4AB233B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f60ee2b0580c9dc52cf59552817c19329e5ebbb9","datavalue":{"value":"computation power","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805444$244DAAF3-3A44-4678-9511-F0D34F4A0276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"122872d3884f9514dfb88fe90bbf0235b954ccd6","datavalue":{"value":"Chomsky hierarchy of languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805444$4D59E802-866D-4CC1-AB2F-974DEA42F802","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":"Q2805444$DBF1685A-79AE-4561-938D-6800EB03EF24","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"04796c0478b0fb9cb98619fbdb099432654437ad","datavalue":{"value":"https://doi.org/10.3233/fi-2015-1196","type":"string"},"datatype":"url"},"type":"statement","id":"Q2805444$314CBAA8-8D37-4EEB-A960-AA3573508B0A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5cb852162fbde5223101da54ffd3bbcb341ab6ce","datavalue":{"value":"W1752758878","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805444$C3C03E06-769C-4CE2-82CE-CEE6E6AE0B94","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5fac0a28d7ca352fae869f85bf2c9c14ce0f4e94","datavalue":{"value":{"text":"Finite automata with multiset memory: a new characterization of Chomsky hierarchy","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2805444$787D0A90-2603-42FE-924E-B733202E4E71","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd6c27bd7e71a77c35e9ff84862225c3a39e95c6","datavalue":{"value":"This paper introduces a new type of computing device and studies its computing power. The usual nondeterministic finite automata are augmented with \\(d\\) memories, each one capable of storing a multiset of natural numbers. These devices are referred to as finite automata with multiset memory (FAMMs). The authors show that FAMMs having \\(0\\), \\(1\\) or \\(d\\geq 2\\) additional storage units accept the classes of regular, context-free or computably enumerable languages, respectively.NEWLINENEWLINEIf the contents of the storage units are bounded exponentially in the length of the input then finite automata with multiset memory accept the class of context-sensitive languages.NEWLINENEWLINEThe last section of the paper deals with classes of languages accepted by FAMMs having further memory restrictions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805444$CE57FF42-878C-45CE-89E2-3A9F837AE002","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"02bc07e7fdf69b7795d4694a59f3d739066e6204","datavalue":{"value":{"entity-type":"item","numeric-id":259038,"id":"Q259038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2805444$003AFE37-05E4-424E-8C9E-23C044E5F847","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1670ce236ed0e35573a072f669611cea8d328780","datavalue":{"value":{"entity-type":"item","numeric-id":3569090,"id":"Q3569090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e03ca20aa925bc2057fbb1b0349f4dde330bfaf0","datavalue":{"value":{"amount":"+0.7666585445404053","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":"Q2805444$92D2F5D8-5827-4E4B-9FC3-617FFCDE7EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be55549f48256497a28d0bf811fb18a68ece4cd2","datavalue":{"value":{"entity-type":"item","numeric-id":1350286,"id":"Q1350286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d68f5e99e1c3950ec632ac68c9458d46ef13fef8","datavalue":{"value":{"amount":"+0.7565062046051025","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":"Q2805444$A678B2F2-6A9F-4445-9D4F-E1682362EFD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f01b17169dba11e4b75f12dbd2c5ad5747d29b39","datavalue":{"value":{"entity-type":"item","numeric-id":4474006,"id":"Q4474006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16c95050a778946c2dda1d91f78a77a61afdb6b6","datavalue":{"value":{"amount":"+0.7532121539115906","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":"Q2805444$C2B51F50-82A1-4162-BFD6-422D7CC899A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f43cae0db1e434561802205bb6d264126b9ec20","datavalue":{"value":{"entity-type":"item","numeric-id":5192935,"id":"Q5192935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63667c395b6b635f58c14f27563bebf15178d171","datavalue":{"value":{"amount":"+0.7301645278930664","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":"Q2805444$BB0323A8-7554-41FB-8144-176372758231","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6381eba784cbc5d6b9a8d5b406ddc7b5c33e313","datavalue":{"value":{"entity-type":"item","numeric-id":553307,"id":"Q553307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d269053516f6ac5dd3176811eac38f2d9744cb31","datavalue":{"value":{"amount":"+0.7287881374359131","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":"Q2805444$3BA48F96-93BC-4855-883A-869EB2980732","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2805444","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2805444"}}}}}