Applicative theories for logarithmic complexity classes

Eberhard, Sebastian (2015). Applicative theories for logarithmic complexity classes. Theoretical Computer Science, 585, pp. 115-135. Elsevier 10.1016/j.tcs.2015.03.007

	Text 1-s2.0-S0304397515002005-main.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (552kB)
Preview	Text accepted.pdf - Accepted Version Available under License Creative Commons: Attribution-Noncommercial-No Derivative Works (CC-BY-NC-ND). Download (483kB) | Preview

We 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.

Interest & Impact

Downloads

205 since deposited on 06 Aug 2015
12 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item