The power of non-determinism in higher-order implicit complexity: characterising complexity classes using non-deterministic cons-free programming

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

The power of non-determinism in higher-order implicit complexity : characterising complexity classes using non-deterministic cons-free programming. / Kop, Cynthia Louisa Martina; Simonsen, Jakob Grue.

Programming Languages and Systems: 26th European Symposium on Programming, ESOP 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017, Proceedings. ed. / Hongseok Yang. Springer, 2017. p. 668-695 (Lecture notes in computer science, Vol. 10201).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Kop, CLM & Simonsen, JG 2017, The power of non-determinism in higher-order implicit complexity: characterising complexity classes using non-deterministic cons-free programming. in H Yang (ed.), Programming Languages and Systems: 26th European Symposium on Programming, ESOP 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017, Proceedings. Springer, Lecture notes in computer science, vol. 10201, pp. 668-695, 26th European Symposium on Programming, Uppsala, Sweden, 22/04/2017. https://doi.org/10.1007/978-3-662-54434-1_25

APA

Kop, C. L. M., & Simonsen, J. G. (2017). The power of non-determinism in higher-order implicit complexity: characterising complexity classes using non-deterministic cons-free programming. In H. Yang (Ed.), Programming Languages and Systems: 26th European Symposium on Programming, ESOP 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017, Proceedings (pp. 668-695). Springer. Lecture notes in computer science Vol. 10201 https://doi.org/10.1007/978-3-662-54434-1_25

Vancouver

Kop CLM, Simonsen JG. The power of non-determinism in higher-order implicit complexity: characterising complexity classes using non-deterministic cons-free programming. In Yang H, editor, Programming Languages and Systems: 26th European Symposium on Programming, ESOP 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017, Proceedings. Springer. 2017. p. 668-695. (Lecture notes in computer science, Vol. 10201). https://doi.org/10.1007/978-3-662-54434-1_25

Author

Kop, Cynthia Louisa Martina ; Simonsen, Jakob Grue. / The power of non-determinism in higher-order implicit complexity : characterising complexity classes using non-deterministic cons-free programming. Programming Languages and Systems: 26th European Symposium on Programming, ESOP 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017, Proceedings. editor / Hongseok Yang. Springer, 2017. pp. 668-695 (Lecture notes in computer science, Vol. 10201).

Bibtex

@inproceedings{0b2710faa93343a3a06c1c740b56e5a6,
title = "The power of non-determinism in higher-order implicit complexity: characterising complexity classes using non-deterministic cons-free programming",
abstract = "We investigate the power of non-determinism in purely functional programming languages with higher-order types. Specifically, we consider cons-free programs of varying data orders, equipped with explicit non-deterministic choice. Cons-freeness roughly means that data constructors cannot occur in function bodies and all manipulation of storage space thus has to happen indirectly using the call stack. While cons-free programs have previously been used by several authors to characterise complexity classes, the work on non-deterministic programs has almost exclusively considered programs of data order 0. Previous work has shown that adding explicit non-determinism to consfree programs taking data of order 0 does not increase expressivity; we prove that this—dramatically—is not the case for higher data orders: adding non-determinism to programs with data order at least 1 allows for a characterisation of the entire class of elementary-time decidable sets. Finally we show how, even with non-deterministic choice, the original hierarchy of characterisations is restored by imposing different restrictions.",
keywords = "Cons-free programming, EXPTIME hierarchy, Implicit computational complexity, Non-deterministic programming, Unitary variables",
author = "Kop, {Cynthia Louisa Martina} and Simonsen, {Jakob Grue}",
year = "2017",
doi = "10.1007/978-3-662-54434-1_25",
language = "English",
isbn = "978-3-662-54433-4",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "668--695",
editor = "Hongseok Yang",
booktitle = "Programming Languages and Systems",
address = "Switzerland",
note = "null ; Conference date: 22-04-2017 Through 29-04-2017",

}

RIS

TY - GEN

T1 - The power of non-determinism in higher-order implicit complexity

AU - Kop, Cynthia Louisa Martina

AU - Simonsen, Jakob Grue

N1 - Conference code: 26

PY - 2017

Y1 - 2017

N2 - We investigate the power of non-determinism in purely functional programming languages with higher-order types. Specifically, we consider cons-free programs of varying data orders, equipped with explicit non-deterministic choice. Cons-freeness roughly means that data constructors cannot occur in function bodies and all manipulation of storage space thus has to happen indirectly using the call stack. While cons-free programs have previously been used by several authors to characterise complexity classes, the work on non-deterministic programs has almost exclusively considered programs of data order 0. Previous work has shown that adding explicit non-determinism to consfree programs taking data of order 0 does not increase expressivity; we prove that this—dramatically—is not the case for higher data orders: adding non-determinism to programs with data order at least 1 allows for a characterisation of the entire class of elementary-time decidable sets. Finally we show how, even with non-deterministic choice, the original hierarchy of characterisations is restored by imposing different restrictions.

AB - We investigate the power of non-determinism in purely functional programming languages with higher-order types. Specifically, we consider cons-free programs of varying data orders, equipped with explicit non-deterministic choice. Cons-freeness roughly means that data constructors cannot occur in function bodies and all manipulation of storage space thus has to happen indirectly using the call stack. While cons-free programs have previously been used by several authors to characterise complexity classes, the work on non-deterministic programs has almost exclusively considered programs of data order 0. Previous work has shown that adding explicit non-determinism to consfree programs taking data of order 0 does not increase expressivity; we prove that this—dramatically—is not the case for higher data orders: adding non-determinism to programs with data order at least 1 allows for a characterisation of the entire class of elementary-time decidable sets. Finally we show how, even with non-deterministic choice, the original hierarchy of characterisations is restored by imposing different restrictions.

KW - Cons-free programming

KW - EXPTIME hierarchy

KW - Implicit computational complexity

KW - Non-deterministic programming

KW - Unitary variables

UR - http://www.scopus.com/inward/record.url?scp=85018691937&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-54434-1_25

DO - 10.1007/978-3-662-54434-1_25

M3 - Article in proceedings

AN - SCOPUS:85018691937

SN - 978-3-662-54433-4

T3 - Lecture notes in computer science

SP - 668

EP - 695

BT - Programming Languages and Systems

A2 - Yang, Hongseok

PB - Springer

Y2 - 22 April 2017 through 29 April 2017

ER -

ID: 178845434