Infinite vs. finite size-bounded randomized computations

作者：

Highlights：

• We generalize the technique of generic words for randomized sweeping automata.

• Superlinear time can make randomized sweeping finite automata exponentially smaller.

• The restriction on time cannot be traded for a more powerful model of randomization.

摘要

•We generalize the technique of generic words for randomized sweeping automata.•Superlinear time can make randomized sweeping finite automata exponentially smaller.•The restriction on time cannot be traded for a more powerful model of randomization.

论文关键词：Probabilistic computations,Las Vegas randomization,Time complexity,Size complexity,Rotating finite automata,Sweeping finite automata

论文评审过程：Received 4 August 2011, Revised 5 October 2013, Accepted 22 November 2013, Available online 6 December 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.11.004