Name
Abstract | ||
|---|---|---|
We develop the theory of index sets in the context of computable analysis considering classes of effectively open sets and computable real-valued functions. First, we construct principal computable numberings for effectively open sets and computable real-valued functions. Then, we calculate the complexity of index sets for important problems such as root realisability, set equivalence and inclusion, function equivalence which naturally arise in continuous constraint solving. Using developed techniques we give a direct proof of the generalised Rice-Shapiro theorem for effectively open sets of Euclidean spaces and present an analogue of Rice's theorem for computable real-valued functions. We illustrate how index sets can be used to estimate complexity of continuous constraints in the settings of the Kleene-Mostowski arithmetical hierarchy. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-662-46823-4_17 | PERSPECTIVES OF SYSTEM INFORMATICS, PSI 2014 |
Field | DocType | Volume |
Algebra,Index set,Complexity of constraint satisfaction,Arithmetical hierarchy,Equivalence (measure theory),Mathematics,Open set,Binary constraint,Computable analysis,Direct proof | Conference | 8974 |
ISSN | Citations | PageRank |
0302-9743 | 3 | 0.46 |
References | Authors | |
11 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Margarita V. Korovina | 1 | 84 | 15.61 |
| Oleg V. Kudinov | 2 | 105 | 15.85 |