Some notes on subword quantification and induction thereof

The first section of this paper consists of a defense of the binary string notation for the formulation of weak theories of arithmetic which have computational significance. We defend that a string language is the most natural framework and that the usual arithmetic setting suffers from some troubles when dealing with very low complexity classes. Having introduced in the first section the theory Th – FO - associated with a rather robust uniform version of the class of problems that can be decided by constant depth, polynomial size circuit families (the so-called AC ⁰-class) - we prove in the second section that the deletion of a crucial axiom from Th – FO results in a theory which is unsuitable from the computational point of view.