ASSOCIATIVE MEMORY ACCEPTORS.
Abstract
The notion of an automaton having an associative memory as its auxiliary storage is presented. This device, called an associative memory acceptor, is then studied under real-time operation. The family L of languages accepted by real-time associative memory acceptors is shown to properly contain the family of languages accepted by 1-tape real-time Turing acceptors. In addition, L is shown to contain a family of languages, each of which is accepted by no n-tape real-time Turing acceptor. A necessary condition is proved for a language to be in L. Next, L is shown to contain an infinite hierarchy of real-time languages. Each member of this hierarchy consists of the family of languages accepted by some real-time associative memory acceptor with a limited number of memory symbols. Following a proof of certain closure properties of L, the above-mentioned necessary condition is used to obtain counter-examples which yield nonclosure results for certain families of the hierarchy. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 08, 1969
- Accession Number
- AD0699592
Entities
People
- Roger Card
Organizations
- System Development Corporation