Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Undecidability in Weihrauch degrees. / Kudinov, Oleg V.; Selivanov, Victor L.; Zhukov, Anton V.
Programs, Proofs, Processes (CiE 2010). 2010. p. 256-265 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6158).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Undecidability in Weihrauch degrees
AU - Kudinov, Oleg V.
AU - Selivanov, Victor L.
AU - Zhukov, Anton V.
PY - 2010/7/29
Y1 - 2010/7/29
N2 - We prove that the 1-quasiorder and the 2-quasiorder of finite k-labeled forests and trees have hereditarily undecidable first-order theories for k ≥ 3. Together with an earlier result of P. Hertling, this implies some undecidability results for Weihrauch degrees. © 2010 Springer-Verlag Berlin Heidelberg.
AB - We prove that the 1-quasiorder and the 2-quasiorder of finite k-labeled forests and trees have hereditarily undecidable first-order theories for k ≥ 3. Together with an earlier result of P. Hertling, this implies some undecidability results for Weihrauch degrees. © 2010 Springer-Verlag Berlin Heidelberg.
KW - 1-quasiorder
KW - 2-quasiorder
KW - labeled forest
KW - theory
KW - undecidability
KW - Weihrauch reducibility
UR - http://www.scopus.com/inward/record.url?scp=77954871598&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-13962-8_29
DO - 10.1007/978-3-642-13962-8_29
M3 - Conference contribution
AN - SCOPUS:77954871598
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 256
EP - 265
BT - Programs, Proofs, Processes (CiE 2010)
T2 - 6th Conference on Computability in Europe, CiE 2010
Y2 - 30 June 2010 through 4 July 2010
ER -
ID: 127086459