首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题: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
国家哲学社会科学文献中心版权所有