ASSOCIATIVE MEMORY ACCEPTORS.
SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF
Pagination or Media Count:
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
- Computer Programming and Software
- Computer Hardware