Paper Info
Title
Remarks on Sigma-definability without the equality test over the Reals
Abstract
In this paper we study properties of Σ–definability over the reals without the equality test which is one of the main concepts in the logical approach to computability over continuous data [Korovina, Margarita V., and Oleg V. Kudinov, The Uniformity Principle for Σ–definability with Applications to Computable Analysis, In Proceedings of CiE'07, Lecture Notes in Computer Science 4497 (2007), 416–425; Korovina, Margarita V., Computational aspects of Σ-definability over the real numbers without the equality test, In Proceedings of CSL'03, Lecture Notes in Computer Science 2803 (2003), 330–344; Korovina, Margarita V., and Oleg V. Kudinov, Semantic characterisations of second-order computability over the real numbers, In Proceedings of CSL'01, Lecture Notes in Computer Science 2142 (2001), 160–172]. In [Korovina, Margarita V., and Oleg V. Kudinov, The Uniformity Principle for Σ–definability with Applications to Computable Analysis, In Proceedings of CiE'07, Lecture Notes in Computer Science 4497 (2007), 416–425] it has been shown that a set B⊂Rn is Σ–definable without the equality test if and only if B is c.e. open. If we allow the equality test, the structure of a Σ–definable subset of Rn can be rather complicated. The next natural question to consider is the following. Is there an effective procedure producing a set which is a maximal c.e. open subset of a given Σ–definable with the equality subset of Rn? It this paper we give the negative answer to this question.
Year
DOI
Venue
2008
10.1016/j.entcs.2008.03.023
Electronic Notes in Theoretical Computer Science
Keywords
DocType
Volume
The real numbers,Σ–definability,computably enumerable open sets
Journal
202
ISSN
Citations 
PageRank 
1571-0661
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Andrei Morozov1263.20
Margarita V. Korovina28415.61