文章基本信息

标题：Randomization in Non-Uniform Finite Automata
本地全文：下载
作者：Pavol ÄZuri{ {s ; Rastislav Kr{'a}loviÄ ; Richard Kr{'a}loviÄ 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：30:1-30:13
DOI：10.4230/LIPIcs.MFCS.2020.30
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：finite automata; non-uniform computation; randomization