Annals of Pure and Applied Logic 161 (3):447-457 (2010)

Abstract
We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Reprint years 2009, 2010
DOI 10.1016/j.apal.2009.07.005
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,226
Through your library

References found in this work BETA

Π01-Classes and Rado's Selection Principle.C. G. Jockusch, A. Lewis & J. B. Remmel - 1991 - Journal of Symbolic Logic 56 (2):684 - 693.
Index Sets for Π01 Classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):3-61.
$\pi^0_1$-Classes And Rado's Selection Principle.C. G. Jockusch, A. Lewis & J. B. Remmel - 1991 - Journal of Symbolic Logic 56 (2):684-693.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Variable-Centered Consistency in Model RB.Liang Li, Tian Liu & Ke Xu - 2013 - Minds and Machines 23 (1):95-103.
Some Natural Decision Problems in Automatic Graphs.Dietrich Kuske & Markus Lohrey - 2010 - Journal of Symbolic Logic 75 (2):678-710.
Coherence: The Price is Right.Paul Thagard - 2012 - Southern Journal of Philosophy 50 (1):42-49.
Effective Search Problems.Martin Kummer & Frank Stephan - 1994 - Mathematical Logic Quarterly 40 (2):224-236.
Recursive Boolean Algebras with Recursive Atoms.Jeffrey B. Remmel - 1981 - Journal of Symbolic Logic 46 (3):595-616.
Inductive Inference and Unsolvability.Leonard M. Adleman & M. Blum - 1991 - Journal of Symbolic Logic 56 (3):891-900.

Analytics

Added to PP index
2013-12-22

Total views
19 ( #579,716 of 2,499,718 )

Recent downloads (6 months)
1 ( #418,066 of 2,499,718 )

How can I increase my downloads?

Downloads

My notes