MULTI-STACK-COUNTER LANGUAGES,

Abstract

A stack-counter acceptor is a stack acceptor in which the storage alphabet is just one letter. The present paper discusses multi-stack-counter acceptors operating in quasi-realtime, i.e., acceptors in which each storage tape is a stack counter and in which there are only a bounded number of consecutive E-moves. It is shown that the quasi-real-time k-stack-counter acceptor is equivalent to one operating in nondeterministic real-time. Lastly, it is shown that acceptance by final state of a k-stack-counter acceptor is equivalent to acceptance by empty tape and final state. (Author)

Document Details

Document Type
Technical Report
Publication Date
Aug 28, 1970
Accession Number
AD0713160

Entities

People

  • Ronald Book
  • Seymour Ginsburg

Organizations

  • System Development Corporation

Tags

DTIC Thesaurus Topics

  • Alphabets
  • Language

Fields of Study

  • Computer science

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Mathematical Modeling and Probability Theory.