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

Cynthia Louisa Martina Kop; Jakob Grue Simonsen

doi:10.1007/978-3-662-54434-1_25

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

Cynthia Louisa Martina Kop^*, Jakob Grue Simonsen

^*Corresponding author for this work

Department of Computer Science

3 Citations (Scopus)

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.

Original language	English
Title of host publication	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
Editors	Hongseok Yang
Number of pages	28
Publisher	Springer
Publication date	2017
Pages	668-695
ISBN (Print)	978-3-662-54433-4
ISBN (Electronic)	978-3-662-54434-1
DOIs	https://doi.org/10.1007/978-3-662-54434-1_25
Publication status	Published - 2017
Event	26th European Symposium on Programming - Uppsala, Sweden Duration: 22 Apr 2017 → 29 Apr 2017 Conference number: 26

Conference

Conference	26th European Symposium on Programming
Number	26
Country/Territory	Sweden
City	Uppsala
Period	22/04/2017 → 29/04/2017

Series	Lecture notes in computer science
Volume	10201
ISSN	0302-9743

Keywords

Cons-free programming
EXPTIME hierarchy
Implicit computational complexity
Non-deterministic programming
Unitary variables

Access to Document

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

http://arxiv.org/pdf/1701.05382

Cite this

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. https://doi.org/10.1007/978-3-662-54434-1_25

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

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

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). doi: 10.1007/978-3-662-54434-1_25

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

@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",

note = "26th European Symposium on Programming ; Conference date: 22-04-2017 Through 29-04-2017",

}

TY - GEN

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

T2 - 26th European Symposium on Programming

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 -

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

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this