
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 readonly automata, that operate synchronously on a single tape, is defined. It is shown that an nhead automation can imitate an automation that has n1 pebbles. Deterministic twohead 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