Two Heads Are Better Than One.
Abstract
A class of multihead read-only automata, that operate synchronously on a single tape, is defined. It is shown that an n-head automation can imitate an automation that has n-1 pebbles. Deterministic two-head automata are described that accept the languages (a sup n)/(b sup n) (or, more generally, the strings on (a,b) having the same number of a's as b's; and similarly for (a sup n)(b sup n)(c sup n), etc.); omega omega; omega(omega sup R); and a(sup(K sup n)), for any fixed k. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1973
- Accession Number
- AD0767080
Entities
People
- Anupam N. Shah
- Azriel Rosenfeld
Organizations
- University of Maryland