Lower bounds on the size of sweeping automata
作者：
Highlights：
•
摘要
A sweeping automaton is a deterministic two-way finite automaton which only changes head direction at the ends of the input tape. It is shown that for every n, there is a language which is accepted by an n-state nondeterministic one-way finite automaton, yet which is not accepted by any sweeping automaton with fewer than 2n states.
论文关键词：
论文评审过程：Received 20 October 1979, Revised 16 May 1980, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(80)90034-3
