The equivalence of theories that characterize ALogTime (Q834715): Difference between revisions

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}\).