Accession Number:

ADA030008

Title:

K+1 Heads are Better than K,

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1976-09-01

Pagination or Media Count:

11.0

Abstract:

There are languages which can be recognized by a deterministic k1-headed one-way finite automaton but which cannot be recognized by a k-headed one-way deterministic or non-deterministic finite automaton. Furthermore, there is a language accepted by a k-headed nondeterministic finite automaton which is accepted by no k-headed deterministic finite automaton. Author

Subject Categories:

  • Numerical Mathematics
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE