MEMORY REQUIREMENTS OF TWO-WAY VERSUS ONE-WAY AUTOMATA.

Abstract

The article presents an example of a two-way automaton which has significantly fewer states than any one-way automaton accepting the same set of tapes. Thus, memory space can be saved by using a two-way automaton. This savings in space, however, is accompanied by an increase in recognition time. (Author)

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1969
Accession Number
AD0684841

Entities

People

  • Bruce H. Barnes

Organizations

  • University of Iowa

Tags

DTIC Thesaurus Topics

  • Automata
  • Recognition

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Marine Propulsion Engineering and Naval Architecture
  • Mathematics or Statistics

Technology Areas

  • Space