DOI

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.
Язык оригиналаанглийский
Название основной публикацииPrograms, Proofs, Processes (CiE 2010)
Страницы256-265
Число страниц10
DOI
СостояниеОпубликовано - 29 июл 2010
Событие6th Conference on Computability in Europe, CiE 2010 - Ponta Delgada, Azores, Португалия
Продолжительность: 30 июн 2010 → 4 июл 2010

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ИздательSpringer Nature
Том6158
ISSN (печатное издание)0302-9743

конференция

конференция6th Conference on Computability in Europe, CiE 2010
Страна/TерриторияПортугалия
ГородPonta Delgada, Azores
Период30/06/10 → 4/07/10

ID: 127086459