ERIC Number: ED043206
Record Type: RIE
Publication Date: 1969-Sep-8
Reference Count: N/A
Associative Memory Acceptors.
The properties of an associative memory are examined in this paper from the viewpoint of automata theory. A device called an associative memory acceptor is 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 one-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. A bibliography is appended. (Author/JY)
Descriptors: Computational Linguistics, Computer Storage Devices, Cybernetics, Programing Languages, Set Theory
Clearinghouse for Federal Scientific and Technical Information, Springfield, Va. 22151 (AD-699 592, MF $.65, HC $3.00)
Publication Type: N/A
Education Level: N/A
Sponsor: Air Force Cambridge Research Labs., L.G. Hanscom Field, MA.
Authoring Institution: System Development Corp., Santa Monica, CA.