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

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

References

• Book , R.V. and Brandenburg , F.J. Equality sets, fixed-point languages, and complexity classes . Proceedings of the Sixth International Colloquium on Automata, Languages and Programming . Graz, Austria. to appear
   Google Scholar
• Culik , K. II . 1978 . The ultimate equivalence problem for DOL systems . Acta Informatica , 10 : 79 – 84 .
   Google Scholar
• Culik , K. II . 1979 . A purely homomorphic characterization of recursively enumerable sets . JACM , 26 : 345 – 350 .
   Google Scholar
• Culik , K. II . 1979 . Some decidability results about regular and pushdown translations . Information Processing Letters , 8 : 5 – 8 .
   Google Scholar
• Culik , K. II and Fris , I. 1977 . The decidability of the equivalence problem for DOL-systems . Information and Control , 35 : 20 – 39 .
   Google Scholar
• Culik K. II Maurer H.A. On simple representations of language families, Revue d’Automatique, Informatique et Recherche Operationelle, to appear
   Google Scholar
• Culik , K. II and Salomaa , A. 1978 . On the decidability of homomorphism equivalence for Languages . JCSS , 17 : 163 – 175 .
   Google Scholar
• Hopcroft , J.E. and Ullman , J.D. 1969 . Formal Languages and their Relation to Automata , Reading, Mass : Addison-Wesley .
   Google Scholar
• Salomaa A. Equality sets for homomorphisms of free monoids Acta Cybernetica to appear
   Google Scholar