Accession Number : AD0699592

Title :   ASSOCIATIVE MEMORY ACCEPTORS.

Descriptive Note : Scientific rept.,

Corporate Author : SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s) : Card,Roger

Report Date : 08 SEP 1969

Pagination or Media Count : 85

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)

Descriptors :   (*COMPUTATIONAL LINGUISTICS, AUTOMATA), MEMORY DEVICES, PROGRAMMING LANGUAGES, REAL TIME, SET THEORY

Subject Categories : Linguistics
      Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE