A homomorphic characterization of time and space complexity classes of languages†
K. Cullik, Nicholas B. Diamond · International Journal of Computer Mathematics · 1980
Recently, it has been shown that for each recursively enumerable language there exists an erasing homomorphism h 0 and homomorphisms h 1,h 2 such that L= h 0(e(h 1,h 2)) where (e(h 1,h 2)) is the set of minimal words on which h 1 and h 2 agree. Here we show that by restrictions on the erasing h 0 we obtain most time-complexity language classes, and by restrictions on the pair (h 1 h 2) we characterize all space complexity language classes.