Memory Requirements of Two-Way Versus One-Way Automata

摘要

The article presents an example of a two-way automaton which has significantly fewer states than any one-way automaton accepting the same set of tapes. Thus, memory space can be saved by using a two-way automaton. This savings in space, however, is accompanied by an increase in recognition time. (Author)