On the power of real-time two-way multihead finite automata with jumps |
| |
| Authors: | Walter J. Savitch Paul M.B. Vitányi |
| |
| Affiliation: | Department of Electrical Engineering & Computer Sciences, University of California, San Diego, La Jolla, CA 92093, U.S.A.;Department of Computer Science, Mathematical Centre, 1098 SJ Amsterdam, The Netherlands |
| |
| Abstract: | ![]()
We investigate the relative power of jumps, nondeterminism, and number of heads for real-time automata. Results include showing that jumps and power that cannot be compensated for by nondeterminism and more heads. We also show that k+1 heads are more powerful than k heads, even if the finite automaton is allowed head to head jumps. |
| |
| Keywords: | Finite automata jumps multihead real time 5.23 5.25 5.26 |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
