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

[img] Text
1-s2.0-S0304397515002005-main.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (552kB)
[img]
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.

Item Type:

Journal Article (Original Article)

Division/Institute:

08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG)
08 Faculty of Science > Institute of Computer Science (INF)

UniBE Contributor:

Eberhard, Sebastian

Subjects:

000 Computer science, knowledge & systems
500 Science > 510 Mathematics

ISSN:

0304-3975

Publisher:

Elsevier

Language:

English

Submitter:

Florian Ranzi

Date Deposited:

06 Aug 2015 16:00

Last Modified:

05 Dec 2022 14:48

Publisher DOI:

10.1016/j.tcs.2015.03.007

BORIS DOI:

10.7892/boris.70704

URI:

https://boris.unibe.ch/id/eprint/70704

Actions (login required)

Edit item Edit item
Provide Feedback