A homomorphic characterization of time and space complexity classes of languages†

†This research was supported by the Natural Sciences and Engineering Research Council of Canada, Grant No. A 7403

Abstract

Recently, it has been shown that for each recursively enumerable language there exists an erasing homomorphism h ₀ and homomorphisms h ₁,h ₂ such that L= h ₀(e(h ₁,h ₂)) where (e(h ₁,h ₂)) is the set of minimal words on which h ₁ and h ₂ agree. Here we show that by restrictions on the erasing h ₀ we obtain most time-complexity language classes, and by restrictions on the pair (h ₁ h ₂) we characterize all space complexity language classes.

Keywords:

• Homomorphic characterization
• complexity classes
• time complexity
• space complexity
• language families

C.R. Categories:

• 5.23
• 5.25

†This research was supported by the Natural Sciences and Engineering Research Council of Canada, Grant No. A 7403

†This research was supported by the Natural Sciences and Engineering Research Council of Canada, Grant No. A 7403

Notes

†This research was supported by the Natural Sciences and Engineering Research Council of Canada, Grant No. A 7403