01150nas a2200133 4500008004100000245006000041210006000101260001900161300001200180490000800192520074100200100002400941856005100965 2015 eng d00aApplicative theories for logarithmic complexity classes0 aApplicative theories for logarithmic complexity classes bElseviercJune a115-1350 v5853 aWe present applicative theories of words corresponding to weak, and especially logarithmic, complexity classes. The theories for the logarithmic hierarchy and alternating logarithmic time formalise function algebras with concatenation recursion as main principle. We present two theories for logarithmic space where the first formalises a new two-sorted algebra which is very similar to Cook and Bellantoni's famous two-sorted algebra B for polynomial time [4]. The second theory describes logarithmic space by formalising concatenation- and sharply bounded recursion. All theories contain the predicates WW representing words, and VV representing temporary inaccessible words. They are inspired by Cantini's theories [6] formalising B.1 aEberhard, Sebastian uhttp://www.iam.unibe.ch/ltgpub/2015/ebat15.pdf