2026-08-11T00:28:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12698 2024-03-06T10:50:36Z ddc:004 open_access

Randomization in Non-Uniform Finite Automata Ďuriš, Pavol Královič, Rastislav Královič, Richard Pardubská, Dana Pašen, Martin Rossmanith, Peter finite automata non-uniform computation randomization The non-uniform version of Turing machines with an extra advice input tape that depends on the length of the input but not the input itself is a well-studied model in complexity theory. We investigate the same notion of non-uniformity in weaker models, namely one-way finite automata. In particular, we are interested in the power of two-sided bounded-error randomization, and how it compares to determinism and non-determinism. We show that for unlimited advice, randomization is strictly stronger than determinism, and strictly weaker than non-determinism. However, when the advice is restricted to polynomial length, the landscape changes: the expressive power of determinism and randomization does not change, but the power of non-determinism is reduced to the extent that it becomes incomparable with randomization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pavol Ďuriš and Rastislav Královič and Richard Královič and Dana Pardubská and Martin Pašen and Peter Rossmanith 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.30 urn:nbn:de:0030-drops-126987 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.30 eng https://creativecommons.org/licenses/by/3.0/legalcode