|
|||||
|
|
Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal |
|
| Authors: | Marcin Balcerzak Damian Niwiński |
| Affiliation: | Faculty of Mathematics, Informatics, and Mechanics, Warsaw University, Poland |
| Abstract: | We prove that limiting the number of reversals from two to one can cause an exponential blow-up in the size of two-way deterministic automaton. |
| Keywords: | Formal languages Regular languages Two-way finite automata Bounded number of reversals |
| 本文献已被 ScienceDirect 等数据库收录！ | |