Images of AFL under certain families of homomorphisms

An AFL is a family of sets of words closed under six basic operations. It is shown that a certain family of homomorphic images of sets in an AFL is an AFL. Then two families of sets related to tape-bounded nondeterministic Turing acceptors are shown to coincide and be an AFL.Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under contract F1962867C0008, the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR Grant No. AF-AFOSR-1203-67A, and by the National Science Foundation, Grant No. GJ454.Part of this work was also done at the System Development Corporation, Santa Monica, Calif.