Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
DOI10.1007/S00236-007-0051-2zbMATH Open1127.68032OpenAlexW2078479724WikidataQ124936233 ScholiaQ124936233MaRDI QIDQ995752FDOQ995752
Authors: C. Iwamoto, Naoki Hatayama, Yoshiaki Nakashiba, Kenichi Morita, Katsunobu Imai 
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
Recommendations
- Fundamentals of Computation Theory
- Machines, Computations, and Universality
- How to translate efficiently extensions of temporal logics into alternating automata
- A timing refinement of intuitionistic proofs and its application to the timing analysis of combinational circuits
- On specifications and proofs of timed circuits
- On log-time alternating Turing machines of alternation depth k
- Completeness for uniformly delayed circuits, a survey
- Distributed Synthesis for Alternating-Time Logics
- scientific article; zbMATH DE number 1189294
- A Unified Translation of Linear Temporal Logic to ω-Automata
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Computational Complexity of Algorithms
- On uniform circuit complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Simulation of Parallel Random Access Machines by Circuits
- Time bounded random access machines
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- A Turing machine time hierarchy
- Title not available (Why is that?)
- A hierarchy for nondeterministic time complexity
- On time hierarchies
- Constructible functions in cellular automata and their applications to hierarchy results
- Hierarchies of Turing machines with restricted tape alphabet size
- A Hierarchy Theorem for Polynomial-Space Recognition
- Title not available (Why is that?)
Cited In (2)
This page was built for publication: Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q995752)
