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.
Original languageEnglish
Title of host publicationPrograms, Proofs, Processes (CiE 2010)
Pages256-265
Number of pages10
DOIs
StatePublished - 29 Jul 2010
Event6th Conference on Computability in Europe, CiE 2010 - Ponta Delgada, Azores, Portugal
Duration: 30 Jun 2010 → 4 Jul 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature
Volume6158
ISSN (Print)0302-9743

Conference

Conference6th Conference on Computability in Europe, CiE 2010
Country/TerritoryPortugal
CityPonta Delgada, Azores
Period30/06/10 → 4/07/10

    Research areas

  • 1-quasiorder, 2-quasiorder, labeled forest, theory, undecidability, Weihrauch reducibility

ID: 127086459