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):

Report Date:

1973-09-01

Pagination or Media Count:

13.0

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 nb sup n or, more generally, the strings on a,b having the same number of as as bs and similarly for a sup nb sup nc sup n, etc. omega omega omegaomega sup R and asupK sup n, for any fixed k. Author

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE