On 0L-Languages

Abstract

In 0L-languages, words are produced from each other by the simultaneous transition of all letters according to a set of production rules; the context is ignored.

(i) 0L-languages are not closed under the operations usually considered.

(ii) 0L-languages over a one-letter alphabet are discussed separately; a characterization is given of a subclass.

(iii) 0L-languages are incomparable with regular sets, incomparable with context-free languages, and strictly included in context-sensitive languages.