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

• Yao,Andrew C.
• Rivest,Ronald L.

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

Descriptors:

• *WORDS(LANGUAGE)
• *AUTOMATA
• COMPUTATIONS
• INPUT OUTPUT PROCESSING
• SEQUENCES
• CONFIGURATIONS
• READING MACHINES
• THEOREMS

Subject Categories:

• Numerical Mathematics
• Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE