More Intensional Versions of Rice’s Theorem

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Standard

More Intensional Versions of Rice’s Theorem. / Moyen, Jean Yves; Simonsen, Jakob Grue.

Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings. red. / Barnaby Martin; Daniël Paulusma; Giuseppe Primiero; Florin Manea. Springer, 2019. s. 217-229 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 11558 LNCS).

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Harvard

Moyen, JY & Simonsen, JG 2019, More Intensional Versions of Rice’s Theorem. i B Martin, D Paulusma, G Primiero & F Manea (red), Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), bind 11558 LNCS, s. 217-229, 15th Conference on Computability in Europe, CiE 2019, Durham, Storbritannien, 15/07/2019. https://doi.org/10.1007/978-3-030-22996-2_19

APA

Moyen, J. Y., & Simonsen, J. G. (2019). More Intensional Versions of Rice’s Theorem. I B. Martin, D. Paulusma, G. Primiero, & F. Manea (red.), Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings (s. 217-229). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind. 11558 LNCS https://doi.org/10.1007/978-3-030-22996-2_19

Vancouver

Moyen JY, Simonsen JG. More Intensional Versions of Rice’s Theorem. I Martin B, Paulusma D, Primiero G, Manea F, red., Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings. Springer. 2019. s. 217-229. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 11558 LNCS). https://doi.org/10.1007/978-3-030-22996-2_19

Author

Moyen, Jean Yves ; Simonsen, Jakob Grue. / More Intensional Versions of Rice’s Theorem. Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings. red. / Barnaby Martin ; Daniël Paulusma ; Giuseppe Primiero ; Florin Manea. Springer, 2019. s. 217-229 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 11558 LNCS).

Bibtex

@inproceedings{8aa823e270c84ba6b13af9a42e999362,
title = "More Intensional Versions of Rice’s Theorem",
abstract = "Classic results in computability theory concern extensional results: the behaviour of partial recursive functions rather than the programs computing them. We prove a generalisation of Rice’s Theorem concerning equivalence classes of programs and show how it can be used to study intensional properties such as time and space complexity. While many results that follow from our general theorems can - and have - been proved by more involved, specialised methods, our results are sufficiently simple that little work is needed to apply them.",
author = "Moyen, {Jean Yves} and Simonsen, {Jakob Grue}",
year = "2019",
doi = "10.1007/978-3-030-22996-2_19",
language = "English",
isbn = "9783030229955",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "217--229",
editor = "Barnaby Martin and Dani{\"e}l Paulusma and Giuseppe Primiero and Florin Manea",
booktitle = "Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings",
note = "15th Conference on Computability in Europe, CiE 2019 ; Conference date: 15-07-2019 Through 19-07-2019",

}

RIS

TY - GEN

T1 - More Intensional Versions of Rice’s Theorem

AU - Moyen, Jean Yves

AU - Simonsen, Jakob Grue

PY - 2019

Y1 - 2019

N2 - Classic results in computability theory concern extensional results: the behaviour of partial recursive functions rather than the programs computing them. We prove a generalisation of Rice’s Theorem concerning equivalence classes of programs and show how it can be used to study intensional properties such as time and space complexity. While many results that follow from our general theorems can - and have - been proved by more involved, specialised methods, our results are sufficiently simple that little work is needed to apply them.

AB - Classic results in computability theory concern extensional results: the behaviour of partial recursive functions rather than the programs computing them. We prove a generalisation of Rice’s Theorem concerning equivalence classes of programs and show how it can be used to study intensional properties such as time and space complexity. While many results that follow from our general theorems can - and have - been proved by more involved, specialised methods, our results are sufficiently simple that little work is needed to apply them.

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

U2 - 10.1007/978-3-030-22996-2_19

DO - 10.1007/978-3-030-22996-2_19

M3 - Article in proceedings

AN - SCOPUS:85069513483

SN - 9783030229955

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 217

EP - 229

BT - Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings

A2 - Martin, Barnaby

A2 - Paulusma, Daniël

A2 - Primiero, Giuseppe

A2 - Manea, Florin

PB - Springer

T2 - 15th Conference on Computability in Europe, CiE 2019

Y2 - 15 July 2019 through 19 July 2019

ER -

ID: 227333975