The equivalence of theories that characterize ALogTime (Q834715)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The equivalence of theories that characterize ALogTime |
scientific article |
Statements
The equivalence of theories that characterize ALogTime (English)
0 references
27 August 2009
0 references
The paper is devoted to theories characterizing the class ALogTime consisting of languages computable by alternating Turing machines. Most attention is paid to Clote's theory ALV\('\). It is shown that ALV\('\) is equivalent to other theories charactyerizing ALogTime, in particular to ALV, T\(^{0}\)NC\(^{0}\), AID + \(\Sigma ^{B}_{0}\)-CA and its two-sorted version VNC\(^{1}\).
0 references
