{"entities":{"Q705065":{"pageid":706914,"ns":120,"title":"Item:Q705065","lastrevid":63759939,"modified":"2026-04-11T15:21:39Z","type":"item","id":"Q705065","labels":{"en":{"language":"en","value":"Comparing verboseness for finite automata and Turing machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2130945"}},"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":"Q705065$CA62CBF8-605A-45D3-AC59-6043A9A7F45B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e15790589a077240f49ec0c88a48321946c2daa","datavalue":{"value":{"text":"Comparing verboseness for finite automata and Turing machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q705065$39F39DA2-D7B1-4F7E-BA61-A4CDFAE41D91","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"91312a8617a58094e9b012d48d6ff195e9d92b99","datavalue":{"value":"1069.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705065$4B72A8CD-5997-4954-B44A-EF5843CA9D56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b2b224aab66ffb4af458805268689af05df667de","datavalue":{"value":{"entity-type":"item","numeric-id":418169,"id":"Q418169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705065$CD9FD8AF-BC0B-42DA-81C6-628F539C7BCF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705065$E629073A-A6E8-4E01-ABAF-0A4E6C9DC400","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e1590bd54b214ce942d11ecbfe0ede26ab9b97ec","datavalue":{"value":{"time":"+2005-01-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q705065$2651BC90-5EEA-49A8-8457-A7490073FCC0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c4afec8a5651b0c5f1e449dbdbae4f5c3e5096fc","datavalue":{"value":"A language \\(L\\) is \\((m, n)\\)-verbose if there is a Turing machine that for any given \\(n\\) input words prints at most \\(m\\) strings of \\(n\\) bits one of which correctly shows which of the words belong to \\(L\\). Let \\(V(m, n)\\) denote the class of all \\((m, n)\\)-verbose languages. Hence, \\(V(2^n, n)\\) contains all languages while \\(V(1, n)\\) consists of the recursive languages \\((n\\geq 1)\\). The polynomial-time verboseness classes \\(V_p(m, n)\\) are obtained by restricting the machines to work in polynomial time. The author defines the corresponding finite automaton verboseness classes \\(V_{fa}(m, n)\\) via multitape finite automata that read the \\(n\\) input words in parallel. The inclusion hierarchy of the classes \\(V_{fa}(m, n)\\) is studied and compared with the corresponding hierarchies of the classes \\(V(m, n)\\) and \\(V_p(m, n)\\). The main result is that \\(V_{fa}(m, n)\\subseteq V_{fa}(h, k)\\) iff \\(V(m, n)\\subseteq V(h, k)\\) for any \\(m\\), \\(n\\), \\(h\\) and \\(k\\). From this fact the author derives a non-speedup theorem for finite automata and, as a corollary of this, a lower bound on the number of bits to be communicated to finite automata checking non-regular protocols.","type":"string"},"datatype":"string"},"type":"statement","id":"Q705065$28E57EA2-3915-4747-BEDE-326C2B9037AD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e07306c48ccd2e9c29ec0a26f6f3afb07223426","datavalue":{"value":{"entity-type":"item","numeric-id":591314,"id":"Q591314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705065$DB04990E-5978-4190-BCE3-590D94B78B94","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705065$00013264-3220-4CC2-81D7-FE37B82434D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705065$63C8DD10-7646-48FD-9BFB-3F3618550E35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705065$C465A900-C7DF-45EA-BABD-5BA8203F188D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705065$0D47D110-9E35-47F9-A0AE-DD1ABC735F29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705065$C31EF0FF-57B1-4DF3-A4FA-C0367DFC1B80","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a5cc5dc074e126401b57c3618013e6d2c09b059c","datavalue":{"value":"2130945","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705065$8E0FDD3E-68A7-4653-B145-9163AA2B9A9E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q705065$4CCE60B8-7F30-4F70-9205-F5C9EF579832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b23780ad6f7e23738af99b2af66b38b7e62a7d4","datavalue":{"value":"verboseness","type":"string"},"datatype":"string"},"type":"statement","id":"Q705065$FD22AA87-3168-451D-A377-35D6E409410D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q705065$32097867-1B4A-436C-9365-B5E53EB3804A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q705065$231A502F-5CC4-410C-B70A-B317A156CAEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7142d39c3323636bd7cc377526eabf4365b5d436","datavalue":{"value":"regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q705065$471E4197-297E-43B5-A646-DC8159F7BE27","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":"Q705065$E2C928DA-D103-4A16-B6D5-D14933C4D6F7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d556eba8c58f62d6c1eb465d17cffefaf96b93da","datavalue":{"value":"https://doi.org/10.1007/s00224-003-1108-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q705065$A00A4440-9CDF-4118-8A93-B17A235ADED3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c65d4701fcbc8894c86b14e81b4d54c783948d9e","datavalue":{"value":"W2071094043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705065$4EFFE279-02E6-41D1-B168-2BC007320D93","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d659ffdfef9b6d0975a40f492a7b0ed63844d392","datavalue":{"value":"10.1007/S00224-003-1108-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705065$1AC946CD-E0EC-4D14-B1E3-12B13518E6B8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c78d1fb6e2f671c0cb9cd357b300694a87511d54","datavalue":{"value":{"entity-type":"item","numeric-id":4736863,"id":"Q4736863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4f475188efae936dc22c6958fbd4e4171d27a3a","datavalue":{"value":{"amount":"+0.9642309546470642","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":"Q705065$B1D7FBB3-1AFA-4C45-940E-581D45CF5F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd667fe53901f8c54d79f5d6e17dd18b2e5165ac","datavalue":{"value":{"entity-type":"item","numeric-id":4699320,"id":"Q4699320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05548441a3f9ef3537bb9f46565eb4a5a09290a9","datavalue":{"value":{"amount":"+0.7625845670700073","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":"Q705065$F7EF47DB-2743-45CC-9BD4-FADFB8737EBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45dbe706d5a16baf96eb3079a06c1f6a8e35cd83","datavalue":{"value":{"entity-type":"item","numeric-id":3821594,"id":"Q3821594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"491f0db5ad16cbe58f754bbd03898a81f9636998","datavalue":{"value":{"amount":"+0.7625840306282043","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":"Q705065$50F62FE0-245A-4835-92DC-01A591816D42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14c49ec5232949a812caeaa3647ea687c9da1ba8","datavalue":{"value":{"entity-type":"item","numeric-id":5048933,"id":"Q5048933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93da8b295c643fac81556e07d907a7fb7df2ed87","datavalue":{"value":{"amount":"+0.7271469235420227","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":"Q705065$CFDB19A3-CBB9-439D-BB1B-0E3AACE44639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06f389c60d3b26e5a41f7a9021de022a3661a1c5","datavalue":{"value":{"entity-type":"item","numeric-id":3034835,"id":"Q3034835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81b119b69a3d9daa82bf86d516a28b589cfca869","datavalue":{"value":{"amount":"+0.7146177291870117","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":"Q705065$9AA76BAA-DB1B-42B8-881B-E58D251EABF4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Comparing verboseness for finite automata and Turing machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Comparing_verboseness_for_finite_automata_and_Turing_machines"}}}}}