Simple Representations of Certain Classes of Languages
Ronald V. Book · Journal of the ACM · 1978
^RSTRACr Using the operation of homomorphlc replication, some restrictions of that operation, and the Boolean operations, simple and uniform characterizations of the following classes of languages are developed.the recurslvely enumerable sets, the arithmetical sets, the languages accepted m real time by nondetermlmstlc reversal-bounded mult~tape Turlng machines, the rudimentary languages, NP, and the extended rudimentary languages