Randomization in Non-Uniform Finite Automata

DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), pp. 13

Abstract

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.

Authors 6

1. Pavol Ďuriš

   Comenius University Bratislava

   Affiliation as printed

   Comenius University in Bratislava, Slovakia

   Comenius University Bratislava, Bratislava, Slovakia

2. Rastislav Kráľovič

   Comenius University Bratislava

   Affiliation as printed

   Comenius University in Bratislava, Slovakia

   Comenius University Bratislava, Bratislava, Slovakia

3. Richard Královič

   ETH Zurich · Google (Switzerland)

   Affiliation as printed

   Google Inc., Zürich, Switzerland

   ETH Zurich, Zurich, Switzerland

4. Dana Pardubská

   Comenius University Bratislava

   Affiliation as printed

   Comenius University in Bratislava, Slovakia

   Comenius University Bratislava, Bratislava, Slovakia

5. Martin Pašen

   Comenius University Bratislava

   Affiliation as printed

   Comenius University in Bratislava, Slovakia

6. Peter Rossmanith Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen, Germany

   RWTH Aachen University, Aachen, Germany