The equivalence of theories that characterize ALogTime
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}\).
scientific article; zbMATH DE number 5598853
scientific article