Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs

DOI10.1007/s00236-007-0051-2zbMath1127.68032OpenAlexW2078479724WikidataQ124936233 ScholiaQ124936233MaRDI QIDQ995752

Kenichi Morita, Katsunobu Imai, Yoshiaki Nakashiba, Naoki Hatayama, Chuzo Iwamoto

Publication date: 10 September 2007

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-007-0051-2

zbMATH Keywords

parallel computationhierarchy

Mathematics Subject Classification ID

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Turing machine time hierarchy
• On time hierarchies
• On uniform circuit complexity
• Hierarchies of Turing machines with restricted tape alphabet size
• A hierarchy for nondeterministic time complexity
• Time bounded random access machines
• Simulation of Parallel Random Access Machines by Circuits
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• A Hierarchy Theorem for Polynomial-Space Recognition
• On the Computational Complexity of Algorithms
• Constructible functions in cellular automata and their applications to hierarchy results

This page was built for publication: Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs