Abstract families of length-preserving processors

摘要

A ”length-preserving processor“, is in essence a nondeterministic linear bounded automaton with auxiliary storage. Length-preserving processors are partitioned into classes according to their methods of handling storage, and each class is termed an “abstract family of length-preserving processors” (AFLP). The smallest AFLP, i.e. the family of linear bounded automata, and the family of context-sensitive languages defined by it are characterized as the smallest families having certain containment and closure properties. These properties motivate the definition of an “abstract family of length-preserving operations,” (AFLO), and a “closed abstract, family of languages” (closed AFL). Every AFLP computes an AFLO and each of a broad class of storage-bounded subfamilies of an AFLP computes an AFLO or a «weak” AFLO. Further, every AFLO is computed by the linear-storage-bounded subfamily of some AFLP. The language associated with an AFLO proves to be a closed AFL. Conversely, every closed AFL defines an AFLO. The notions of “principal AFLO” and “principal closed AFL” are introduced. Applications are made to writing acceptor theory.