Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
From MaRDI portal
Publication:995752
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
