The equivalence of theories that characterize ALogTime (Q834715): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 14:51, 30 January 2024
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
