{"entities":{"Q579936":{"pageid":581703,"ns":120,"title":"Item:Q579936","lastrevid":62944833,"modified":"2026-04-11T09:09:27Z","type":"item","id":"Q579936","labels":{"en":{"language":"en","value":"A lower bound for probabilistic algorithms for finite state machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016197"}},"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":"Q579936$DE6E0DFA-6351-41E6-9395-00FF4A844918","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7d142c946edc8bc41b399d5afc7bf4c66f219311","datavalue":{"value":{"text":"A lower bound for probabilistic algorithms for finite state machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q579936$A8C52AD9-FD70-4CD6-A686-EFCE89F96BD9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"45fd45035033e64b2d51a9d9a8c03e61cfe2a74a","datavalue":{"value":"0625.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579936$C4D2181E-3DF1-4C90-9E8E-936073F5A849","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b660e300e6a24315b5abaf59a91faa68dd49c7e7","datavalue":{"value":"10.1016/0022-0000(86)90045-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579936$CC32C5E6-3D41-4F60-AED0-9CE359F53D9E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f630fca35882c22c73e140b0b5e94a8b8f87f8b","datavalue":{"value":{"entity-type":"item","numeric-id":579934,"id":"Q579934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$D618A9C9-7BF5-4C3F-B7BB-A0C9FCE559F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e537f4f44d78109e9898411963fbc38422a3a839","datavalue":{"value":{"entity-type":"item","numeric-id":579935,"id":"Q579935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$705A33D5-DC0A-470A-BA68-5319ED50D2D0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$B6C820D6-8952-4AEF-A577-5B6F1816F394","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q579936$CB552F5B-882B-4EB8-937C-704F8F4D8713","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d4c002c84afdccb75948b196362089c9238fab61","datavalue":{"value":"\\textit{R. Freivalds} [Lect. Notes Comput. Sci. 118, 33-45 (1981; Zbl 0486.68045)] recently reported a construction of a 2-way probabilistic finite automaton M that recognizes the set \\(\\{a^ mb^ m:m\\geq 1\\}\\) with arbitrarily small probability of error. This result implies that probabilistic machines of this type are more powerful than their deterministic, nondeterministic, and alternating counterparts. Freivalds' construction has a negative feature: the automaton M runs in \\(\\Omega (2^{n/2}n)\\) expected time in the worst case on inputs of length n. We show that it is impossible to do significantly better. Specifically, no 2-way probabilistic finite automaton that runs in exp(o(n)) expected time recognizes \\(\\{a^ mb^ m:m\\geq 1\\}\\) with probability of error bounded away from \\(1/2\\). In passing we derive results on the densities of regular sets, the fine structure of Freivalds' construction, and the behavior of random walks controlled by Markov chains.","type":"string"},"datatype":"string"},"type":"statement","id":"Q579936$742F45A4-472C-401C-BCBD-935DF42C3032","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579936$101A630B-D873-4AB7-8C34-244ACD80B26B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579936$5DEE35A6-7CB2-456F-9E60-215B05D5BA0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e52a86b600bbb05d9a7823bf91d423713b4b70ab","datavalue":{"value":"60G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579936$0F8E94B0-0778-496B-B470-55CB1CFB6A0B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dfa0525a169f62c844dc4d289940989b6c4d53df","datavalue":{"value":"4016197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579936$A135D735-F301-40AB-8026-EF54A59CE7C3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad923100a8b3b2293a389d415cd644130961e6c1","datavalue":{"value":"2-way probabilistic finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q579936$73054199-FFBE-465B-BA06-EEDAC2FDC77B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab6798eae4b240fd576821fb7242c02fc42ef835","datavalue":{"value":"densities of regular sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q579936$649D03EE-69D4-4C93-8BDD-EDB46E3BC8F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8acd06e42745ce31cd5a165a23a42eaa242f9a3a","datavalue":{"value":"behavior of random walks controlled by Markov chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q579936$EE4559A3-2071-4256-9AAD-F60CD670D568","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":"Q579936$591D048A-189C-4340-A092-C5F06CDD727A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"08de5f844c2c54a50c59cbc609e631dc5f5d2a9e","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90045-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q579936$67F5DF98-A87F-429C-A216-03966DBB6662","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a764b99297dec65e0b365d37264176037be6334c","datavalue":{"value":"W2073696431","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579936$FC22CEAC-9BDC-48E4-A28C-F1E2EC9C4DDF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e4a1dd34efab04d46145770e771be8bf407a4ee","datavalue":{"value":{"entity-type":"item","numeric-id":795406,"id":"Q795406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$FC25B08B-EB17-4E82-A3EA-C8B297B9E1E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"907002c1fc8b99fdc9be847bf69a2997d19c0276","datavalue":{"value":{"entity-type":"item","numeric-id":3947125,"id":"Q3947125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$9EC3979B-245E-4D00-8240-F3C36F7B719B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b58fa67202575a971e472065d0ce3518d3d99d2","datavalue":{"value":{"entity-type":"item","numeric-id":4177654,"id":"Q4177654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$E158417C-EC4C-4A1A-88DB-13E2ADF2252D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6e49316340cae5be444a30d61ee7f919a8e7b73","datavalue":{"value":{"entity-type":"item","numeric-id":3939931,"id":"Q3939931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$57AF4977-EA28-4B33-B5A1-28B9CFFD6632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$78C835E7-C402-4D9C-8FA6-F2989FCF015D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"548d853a18eb713f9463402e105feb27bfd6a78f","datavalue":{"value":{"entity-type":"item","numeric-id":3849299,"id":"Q3849299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$F40ABA52-201B-4118-B22F-46CF0601E16C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67c9cbfb57c23127028760f3406ad25be536064c","datavalue":{"value":{"entity-type":"item","numeric-id":5896278,"id":"Q5896278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$BA740BB7-9BB8-4A56-AB27-3314F3BDB20F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76c2e166c21268174f22435e129942ae345904e6","datavalue":{"value":{"entity-type":"item","numeric-id":3325044,"id":"Q3325044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$7174C784-73E5-4EF4-8870-45A6188F9ED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e004b59f31388690d9d9d56b5440c3449cc5b76c","datavalue":{"value":{"entity-type":"item","numeric-id":3227952,"id":"Q3227952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$FA2DFD6F-5025-4CA7-938E-E2A919B956D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13ecf59f9a4d1b7659a1683859f2c9d3ac797ae0","datavalue":{"value":{"entity-type":"item","numeric-id":5572344,"id":"Q5572344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$2F76CD29-3B6B-44D0-9DCC-A244CCE85637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45cd9f9b131fbd39ce6e07626d4b3ef52c602fd5","datavalue":{"value":{"entity-type":"item","numeric-id":5598777,"id":"Q5598777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$D2DB7840-E573-41E9-905A-2B4A7461D5FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eb6290412741acf231ec58be371ffd9c5ecc534","datavalue":{"value":{"entity-type":"item","numeric-id":4155837,"id":"Q4155837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$0A767FBA-3D92-4F0A-9371-2CD4CCDF5F0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2721c702dd018b6c82dceadd8f3e8916a3a56b42","datavalue":{"value":{"entity-type":"item","numeric-id":1157624,"id":"Q1157624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579936$7E77CCBD-F4E2-4F4F-9031-FF09205EA55A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19756401e6cf3b66a884bcd0beb4da96d3b597e4","datavalue":{"value":{"entity-type":"item","numeric-id":3495661,"id":"Q3495661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d9d93a766ad198f4adef4659265f170c433e08f","datavalue":{"value":{"amount":"+0.8631330132484436","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":"Q579936$608C90AC-8C3D-490C-838C-9FA1B9A17DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a1c74aeca0323d08a7c23a59bb81ff5cb7b871e","datavalue":{"value":{"entity-type":"item","numeric-id":3319779,"id":"Q3319779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"776ce566bb88ec5a18f151c18027d4f49c63358d","datavalue":{"value":{"amount":"+0.8455009460449219","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":"Q579936$D11B12E1-D73B-41D1-BB25-55B6AD0BBDCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa8a361f4adcd12f8657b809f8cc168dee87b5d","datavalue":{"value":{"entity-type":"item","numeric-id":4036562,"id":"Q4036562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d04e94deccae4c37d52c2fd19fa2f4f0aa8ddf1","datavalue":{"value":{"amount":"+0.840871274471283","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":"Q579936$089F7EE4-FAEF-433D-A59C-A17ACA482450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2720e888ba97da74fc4e3cf8e6a66cb1c8b721e9","datavalue":{"value":{"entity-type":"item","numeric-id":4256643,"id":"Q4256643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ea4709ff5975b46a92011f3a1ecc530c2a1ed03","datavalue":{"value":{"amount":"+0.830924391746521","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":"Q579936$8FB2D76F-83EE-4909-82A9-D6BC0B91F05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66f8bbc48e0cd6dea702c6a4fa9ff9a3c411683d","datavalue":{"value":{"entity-type":"item","numeric-id":6487443,"id":"Q6487443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"744bf798df11293d2bad0daa2321c29c72ff482d","datavalue":{"value":{"amount":"+0.8300479054450989","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":"Q579936$32CF25AF-AA88-4ACD-B370-36F7C29AAC3E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A lower bound for probabilistic algorithms for finite state machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_lower_bound_for_probabilistic_algorithms_for_finite_state_machines"}}}}}