Back to Search
Start Over
On Infinitary Rational Relations and Borel Sets
- Source :
- Proceedings of the International Conference DMTCS'03, Fourth International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS'03, 7-12 July 2003, Dijon, France., Fourth International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS'03, 7-12 July 2003, Dijon, France., 2003, France. pp.155-167, Discrete Mathematics and Theoretical Computer Science ISBN: 9783540405054, DMTCS
- Publication Year :
- 2010
-
Abstract
- International audience; We prove in this paper that there exists some infinitary rational relations which are Sigma^0_3-complete Borel sets and some others which are Pi^0_3-complete. This implies that there exists some infinitary rational relations which are Delta^0_4-sets but not (Sigma^0_3U Pi^0_3)-sets. These results give additional answers to questions of Simonnet and of Lescow and Thomas.
- Subjects :
- FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Computer Science - Logic in Computer Science
Existential quantification
infinitary rational relations
0102 computer and information sciences
02 engineering and technology
Computational Complexity (cs.CC)
Topological space
01 natural sciences
Borel equivalence relation
Borel hierarchy
Borel sets
Computer Science::Logic in Computer Science
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Mathematics
Discrete mathematics
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Mathematics - Logic
16. Peace & justice
Logic in Computer Science (cs.LO)
[MATH.MATH-LO]Mathematics [math]/Logic [math.LO]
Mathematics::Logic
Computer Science - Computational Complexity
010201 computation theory & mathematics
020201 artificial intelligence & image processing
Rational relation
Logic (math.LO)
Borel set
topological properties
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-540-40505-4
- ISBNs :
- 9783540405054
- Database :
- OpenAIRE
- Journal :
- Proceedings of the International Conference DMTCS'03, Fourth International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS'03, 7-12 July 2003, Dijon, France., Fourth International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS'03, 7-12 July 2003, Dijon, France., 2003, France. pp.155-167, Discrete Mathematics and Theoretical Computer Science ISBN: 9783540405054, DMTCS
- Accession number :
- edsair.doi.dedup.....9242f3af52d0f2d5482a8ef8eaf78878