The equivalence of theories that characterize ALogTime
type: Item
instance of: scholarly article
title: The equivalence of theories that characterize ALogTime
zbMATH Open document ID: 1172.03023
author: N. E. Zubov
published in: Archive for Mathematical Logic
publication date: 2009-08-27T00:00:00Z
review text: 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}\).
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 5598853
reviewed by: Roman Murawski
MaRDI profile type: Publication
full work available at URL: s00153-009-0136-4
OpenAlex ID: W2084344766
cites work: A bounded arithmetic AID for Frege systems
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: On uniformity within \(NC^ 1\)
cites work: Q3794177
cites work: ALOGTIME and a conjecture of S. A. Cook
cites work: Q4035303
cites work: Q3140635
cites work: Bounded arithmetic for NC, ALogTIME, L and NL
cites work: Q4850548
cites work: Q4375787
cites work: Q5465359
cites work: Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
cites work: Q5286672
cites work: Q4227581
cites work: Exponentiation and second-order bounded arithmetic
cites work: Q4856172
cites work: Theories for TC0 and Other Small Complexity Classes
cites work: Q3140640
cites work: Undirected ST-connectivity in log-space
cites work: On uniform circuit complexity
cites work: Q3140644
cites work: Notes on polynomially bounded arithmetic
DOI: 10.1007/S00153-009-0136-4
description: scientific article; zbMATH DE number 5598853