One-Way Bounded Cellular Acceptors.

Abstract

The formal language recognition capabilities of one-dimensional one-way bounded cellular automata are studied. In particular, their relationships to real-time two-way bounded cellular acceptors, real-time iterative acceptors, real-time on-line multitape Turing acceptors, and one-way multihead finite acceptors are investigated. It is shown that the Dyck, linear, standard, and bracketed context-free languages are accepted in real-time by one-way bounded cellular acceptors. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1978
Accession Number
ADA060427

Entities

People

  • Charles R. Dyer

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Automata
  • Computations
  • Computer Science
  • Formal Languages
  • Grammars
  • Language
  • Machines
  • Pattern Recognition
  • Recognition
  • Scientific Research
  • Sequences
  • Simulations
  • Standards
  • Transitions
  • Two Dimensional

Readers

  • Computational Linguistics
  • Mathematical Modeling and Probability Theory.