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

DOI10.1080/00207168008803207zbMath0444.68035OpenAlexW2082323186WikidataQ122660473 ScholiaQ122660473MaRDI QIDQ3888530

N. D. Diamond, Karel II Culik

Publication date: 1980

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168008803207

zbMATH Keywords

homomorphismstime complexitycomplexity classesspace complexitymachine independent characterizationnondeterministic online Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

Representations of language families by homomorphic equality operations and generalized equality sets, A representation of recursively enumerable languages by two homomorphisms and a quotient, 2DST mappings of languages and related problems, Unnamed Item, Checking sets, test sets, rich languages and commutatively closed languages

Cites Work

• Unnamed Item
• Unnamed Item
• The ultimate equivalence problem for DOL systems
• On the decidability of homomorphism equivalence for languages
• Some decidability results about regular and pushdown translations
• Equality Sets and Complexity Classes
• The decidability of the equivalence problem for DOL-systems
• A Purely Homomorphic Characterization of Recursively Enumerable Sets