Accession Number : AD0767080

Title :   Two Heads Are Better Than One.

Descriptive Note : Technical rept.,

Corporate Author : MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER

Personal Author(s) : Shah,Anupam N. ; Rosenfeld,Azriel

Report Date : SEP 1973

Pagination or Media Count : 13

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)

Descriptors :   (*COMPUTER PROGRAMMING, *MATHEMATICAL LOGIC), AUTOMATA, SET THEORY, THEOREMS

Subject Categories : Theoretical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE