The equivalence of theories that characterize ALogTime (Q834715)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The equivalence of theories that characterize ALogTime |
scientific article; zbMATH DE number 5598853
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The equivalence of theories that characterize ALogTime |
scientific article; zbMATH DE number 5598853 |
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
0 references
0 references
0.762024998664856
0 references
0.7606579065322876
0 references
0.7461739182472229
0 references
0.7461739182472229
0 references
0.736599862575531
0 references
