Π10 sets and tilings

Emmanuel Jeandel; Pascal Vanier

doi:10.1007/978-3-642-20877-5_24

Π₁⁰ sets and tilings

Emmanuel Jeandel, Pascal Vanier

LIF

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

Abstract

In this paper, we prove that given any Π₁⁰ subset P of {0,1}^ℕ there is a tileset τ with a countable set of configurations C such that P is recursively homeomorphic to C \ U where U is a computable set of configurations. As a consequence, if P is countable, this tileset has the exact same set of Turing degrees.

Original language	English
Title of host publication	Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings
Publisher	Springer Verlag
Pages	230-239
Number of pages	10
ISBN (Print)	9783642208768
DOIs	https://doi.org/10.1007/978-3-642-20877-5_24
Publication status	Published - 1 Jan 2011
Externally published	Yes
Event	8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 - Tokyo, Japan Duration: 23 May 2011 → 25 May 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6648 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011
Country/Territory	Japan
City	Tokyo
Period	23/05/11 → 25/05/11

Access to Document

10.1007/978-3-642-20877-5_24

Cite this

Jeandel, E., & Vanier, P. (2011). Π₁⁰ sets and tilings. In Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings (pp. 230-239). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6648 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-20877-5_24

@inproceedings{bc9fbbf3626745ce81e2a43a5bdaa1cb,

title = "Π10 sets and tilings",

abstract = "In this paper, we prove that given any Π10 subset P of \{0,1\}ℕ there is a tileset τ with a countable set of configurations C such that P is recursively homeomorphic to C \textbackslash{} U where U is a computable set of configurations. As a consequence, if P is countable, this tileset has the exact same set of Turing degrees.",

author = "Emmanuel Jeandel and Pascal Vanier",

year = "2011",

month = jan,

day = "1",

doi = "10.1007/978-3-642-20877-5\_24",

language = "English",

isbn = "9783642208768",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "230--239",

booktitle = "Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings",

note = "8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 ; Conference date: 23-05-2011 Through 25-05-2011",

}

Jeandel, E & Vanier, P 2011, Π₁⁰ sets and tilings. in Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6648 LNCS, Springer Verlag, pp. 230-239, 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011, Tokyo, Japan, 23/05/11. https://doi.org/10.1007/978-3-642-20877-5_24

Π₁⁰ sets and tilings. / Jeandel, Emmanuel; Vanier, Pascal.
Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings. Springer Verlag, 2011. p. 230-239 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6648 LNCS).

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

TY - GEN

T1 - Π10 sets and tilings

AU - Jeandel, Emmanuel

AU - Vanier, Pascal

PY - 2011/1/1

Y1 - 2011/1/1

N2 - In this paper, we prove that given any Π10 subset P of {0,1}ℕ there is a tileset τ with a countable set of configurations C such that P is recursively homeomorphic to C \ U where U is a computable set of configurations. As a consequence, if P is countable, this tileset has the exact same set of Turing degrees.

AB - In this paper, we prove that given any Π10 subset P of {0,1}ℕ there is a tileset τ with a countable set of configurations C such that P is recursively homeomorphic to C \ U where U is a computable set of configurations. As a consequence, if P is countable, this tileset has the exact same set of Turing degrees.

U2 - 10.1007/978-3-642-20877-5_24

DO - 10.1007/978-3-642-20877-5_24

M3 - Conference contribution

AN - SCOPUS:79955790507

SN - 9783642208768

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

SP - 230

EP - 239

BT - Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings

PB - Springer Verlag

T2 - 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011

Y2 - 23 May 2011 through 25 May 2011

ER -