An implicit characterization of the polynomial-time decidable sets by cons-free rewriting

Daniel Bruno de Carvalho; Jakob Grue Simonsen

doi:10.1007/978-3-319-08918-8_13

An implicit characterization of the polynomial-time decidable sets by cons-free rewriting

Daniel Bruno de Carvalho, Jakob Grue Simonsen

Department of Computer Science

4 Citations (Scopus)

Abstract

We define the class of constrained cons-free rewriting systems and show that this class characterizes P, the set of languages decidable in polynomial time on a deterministic Turing machine. The main novelty of the characterization is that it allows very liberal properties of term rewriting, in particular non-deterministic evaluation: no reduction strategy is enforced, and systems are allowed to be non-confluent.

Original language	English
Title of host publication	Rewriting and typed lambda calculi : Joint International Conference, RTA-TLCA 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings
Editors	Gilles Dowek
Number of pages	15
Publisher	Springer Science+Business Media
Publication date	2014
Pages	179-193
ISBN (Print)	978-3-319-08917-1
ISBN (Electronic)	978-3-319-08918-8
DOIs	https://doi.org/10.1007/978-3-319-08918-8_13
Publication status	Published - 2014
Event	Joint International Conference, RTA-TLCA 2014 - Vienna, Austria Duration: 14 Jul 2014 → 17 Jul 2014

Conference

Conference	Joint International Conference, RTA-TLCA 2014
Country/Territory	Austria
City	Vienna
Period	14/07/2014 → 17/07/2014

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

Access to Document

10.1007/978-3-319-08918-8_13

Cite this

de Carvalho, D. B., & Simonsen, J. G. (2014). An implicit characterization of the polynomial-time decidable sets by cons-free rewriting. In G. Dowek (Ed.), Rewriting and typed lambda calculi: Joint International Conference, RTA-TLCA 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings (pp. 179-193). Springer Science+Business Media. Lecture notes in computer science Vol. 8560 https://doi.org/10.1007/978-3-319-08918-8_13

An implicit characterization of the polynomial-time decidable sets by cons-free rewriting. / de Carvalho, Daniel Bruno; Simonsen, Jakob Grue.

Rewriting and typed lambda calculi: Joint International Conference, RTA-TLCA 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings. ed. / Gilles Dowek. Springer Science+Business Media, 2014. p. 179-193 (Lecture notes in computer science, Vol. 8560).

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

de Carvalho, DB & Simonsen, JG 2014, An implicit characterization of the polynomial-time decidable sets by cons-free rewriting. in G Dowek (ed.), Rewriting and typed lambda calculi: Joint International Conference, RTA-TLCA 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings. Springer Science+Business Media, Lecture notes in computer science, vol. 8560, pp. 179-193, Joint International Conference, RTA-TLCA 2014, Vienna, Austria, 14/07/2014. https://doi.org/10.1007/978-3-319-08918-8_13

de Carvalho DB, Simonsen JG. An implicit characterization of the polynomial-time decidable sets by cons-free rewriting. In Dowek G, editor, Rewriting and typed lambda calculi: Joint International Conference, RTA-TLCA 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings. Springer Science+Business Media. 2014. p. 179-193. (Lecture notes in computer science, Vol. 8560). doi: 10.1007/978-3-319-08918-8_13

de Carvalho, Daniel Bruno ; Simonsen, Jakob Grue. / An implicit characterization of the polynomial-time decidable sets by cons-free rewriting. Rewriting and typed lambda calculi: Joint International Conference, RTA-TLCA 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings. editor / Gilles Dowek. Springer Science+Business Media, 2014. pp. 179-193 (Lecture notes in computer science, Vol. 8560).

@inproceedings{8e34c95c09324610aa098a861aaee84e,

title = "An implicit characterization of the polynomial-time decidable sets by cons-free rewriting",

abstract = "We define the class of constrained cons-free rewriting systems and show that this class characterizes P, the set of languages decidable in polynomial time on a deterministic Turing machine. The main novelty of the characterization is that it allows very liberal properties of term rewriting, in particular non-deterministic evaluation: no reduction strategy is enforced, and systems are allowed to be non-confluent.",

author = "{de Carvalho}, {Daniel Bruno} and Simonsen, {Jakob Grue}",

year = "2014",

doi = "10.1007/978-3-319-08918-8_13",

language = "English",

isbn = "978-3-319-08917-1",

series = "Lecture notes in computer science",

publisher = "Springer Science+Business Media",

pages = "179--193",

editor = "Gilles Dowek",

booktitle = "Rewriting and typed lambda calculi",

address = "Singapore",

note = "Joint International Conference, RTA-TLCA 2014 ; Conference date: 14-07-2014 Through 17-07-2014",

}

TY - GEN

T1 - An implicit characterization of the polynomial-time decidable sets by cons-free rewriting

AU - de Carvalho, Daniel Bruno

AU - Simonsen, Jakob Grue

PY - 2014

Y1 - 2014

N2 - We define the class of constrained cons-free rewriting systems and show that this class characterizes P, the set of languages decidable in polynomial time on a deterministic Turing machine. The main novelty of the characterization is that it allows very liberal properties of term rewriting, in particular non-deterministic evaluation: no reduction strategy is enforced, and systems are allowed to be non-confluent.

AB - We define the class of constrained cons-free rewriting systems and show that this class characterizes P, the set of languages decidable in polynomial time on a deterministic Turing machine. The main novelty of the characterization is that it allows very liberal properties of term rewriting, in particular non-deterministic evaluation: no reduction strategy is enforced, and systems are allowed to be non-confluent.

U2 - 10.1007/978-3-319-08918-8_13

DO - 10.1007/978-3-319-08918-8_13

M3 - Article in proceedings

SN - 978-3-319-08917-1

T3 - Lecture notes in computer science

SP - 179

EP - 193

BT - Rewriting and typed lambda calculi

A2 - Dowek, Gilles

PB - Springer Science+Business Media

T2 - Joint International Conference, RTA-TLCA 2014

Y2 - 14 July 2014 through 17 July 2014

ER -

An implicit characterization of the polynomial-time decidable sets by cons-free rewriting

Abstract

Conference

Access to Document

Fingerprint

Cite this