Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
type: Item
instance of: scholarly article
title: Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
zbMATH Open document ID: 1127.68032
author: C. Iwamoto
author: Naoki Hatayama
author: Yoshiaki Nakashiba
author: Kenichi Morita
author: Katsunobu Imai
published in: Acta Informatica
publication date: 2007-09-10T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 5189127
zbMATH Keywords: parallel computation
zbMATH Keywords: hierarchy
MaRDI profile type: Publication
full work available at URL: s00236-007-0051-2
OpenAlex ID: W2078479724
Wikidata QID: Q124936233
cites work: Q4091421
cites work: A hierarchy for nondeterministic time complexity
cites work: Time bounded random access machines
cites work: Q5636862
cites work: On the Computational Complexity of Algorithms
cites work: Q3862379
cites work: A Hierarchy Theorem for Polynomial-Space Recognition
cites work: Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
cites work: Hierarchies of Turing machines with restricted tape alphabet size
cites work: Q4253321
cites work: Constructible functions in cellular automata and their applications to hierarchy results
cites work: Q4385522
cites work: On time hierarchies
cites work: On uniform circuit complexity
cites work: Simulation of Parallel Random Access Machines by Circuits
cites work: Q3854629
cites work: A Turing machine time hierarchy
DOI: 10.1007/S00236-007-0051-2
Recommended article: Fundamentals of Computation Theory
Recommended article: Machines, Computations, and Universality
Recommended article: How to Translate Efficiently Extensions of Temporal Logics into Alternating Automata
Recommended article: A timing refinement of intuitionistic proofs and its application to the timing analysis of combinational circuits
Recommended article: On specifications and proofs of timed circuits
Recommended article: On log-time alternating Turing machines of alternation depth k
Recommended article: Completeness for uniformly delayed circuits, a survey
Recommended article: Distributed Synthesis for Alternating-Time Logics
Recommended article: Q3839068
Recommended article: A Unified Translation of Linear Temporal Logic to ω-Automata
description: scientific article; zbMATH DE number 5189127