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

DOI10.1007/S00236-007-0051-2MaRDI QIDQ995752zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

hierarchyparallel computation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

Cites work

• scientific article; zbMATH DE number 3655356 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1322310 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• A Hierarchy Theorem for Polynomial-Space Recognition
• A Turing machine time hierarchy
• A hierarchy for nondeterministic time complexity
• Constructible functions in cellular automata and their applications to hierarchy results
• Hierarchies of Turing machines with restricted tape alphabet size
• On the Computational Complexity of Algorithms
• On time hierarchies
• On uniform circuit complexity
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• Simulation of Parallel Random Access Machines by Circuits
• Time bounded random access machines

Cited in

(2)

• Machines, Computations, and Universality
• Fundamentals of Computation Theory

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)