  The main contribution of this work is the definition of a quantifier-free
string theory T_1 suitable for formalizing ALOGTIME reasoning. After describing
L_1 -- a new, simple, algebraic characterization of the complexity class
ALOGTIME based on strings instead of numbers -- the theory T_1 is defined
(based on L_1), and a detailed formal development of T_1 is given.
  Then, theorems of T_1 are shown to translate into families of propositional
tautologies that have uniform polysize Frege proofs, T_1 is shown to prove the
soundness of a particular Frege system F, and F is shown to provably p-simulate
any proof system whose soundness can be proved in T_1. Finally, T_1 is compared
with other theories for ALOGTIME reasoning in the literature.
  To our knowledge, this is the first formal theory for ALOGTIME reasoning
whose basic objects are strings instead of numbers, and the first
quantifier-free theory formalizing ALOGTIME reasoning in which a direct proof
of the soundness of some Frege system has been given (in the case of
first-order theories, such a proof was first given by Arai for his theory AID).
Also, the polysize Frege proofs we give for the propositional translations of
theorems of T_1 are considerably simpler than those for other theories, and so
is our proof of the soundness of a particular F-system in T_1. Together with
the simplicity of T_1's recursion schemes, axioms, and rules these facts
suggest that T_1 is one of the most natural theories available for ALOGTIME
reasoning.
