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

Datalogisk Institut

4 Citationer (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.

Originalsprog	Engelsk
Titel	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
Redaktører	Gilles Dowek
Antal sider	15
Forlag	Springer Science+Business Media
Publikationsdato	2014
Sider	179-193
ISBN (Trykt)	978-3-319-08917-1
ISBN (Elektronisk)	978-3-319-08918-8
DOI	https://doi.org/10.1007/978-3-319-08918-8_13
Status	Udgivet - 2014
Begivenhed	Joint International Conference, RTA-TLCA 2014 - Vienna, Østrig Varighed: 14 jul. 2014 → 17 jul. 2014

Konference

Konference	Joint International Conference, RTA-TLCA 2014
Land/Område	Østrig
By	Vienna
Periode	14/07/2014 → 17/07/2014

Navn	Lecture notes in computer science
Vol/bind	8560
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

de Carvalho, D. B., & Simonsen, J. G. (2014). An implicit characterization of the polynomial-time decidable sets by cons-free rewriting. I G. Dowek (red.), 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 (s. 179-193). Springer Science+Business Media. Lecture notes in computer science Bind 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. red. / Gilles Dowek. Springer Science+Business Media, 2014. s. 179-193 (Lecture notes in computer science, Bind 8560).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

de Carvalho, DB & Simonsen, JG 2014, An implicit characterization of the polynomial-time decidable sets by cons-free rewriting. i G Dowek (red.), 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, bind 8560, s. 179-193, Joint International Conference, RTA-TLCA 2014, Vienna, Østrig, 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. I Dowek G, red., 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. s. 179-193. (Lecture notes in computer science, Bind 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. red. / Gilles Dowek. Springer Science+Business Media, 2014. s. 179-193 (Lecture notes in computer science, Bind 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater