Computable Approximations of Semicomputable Graphs
Abstract
In this work, we study the computability of topological graphs, which are obtained by gluing arcs and rays together at their endpoints. We prove that every semicomputable graph in a computable metric space can be approximated, with arbitrary precision, by its computable subgraph with computable endpoints.
Fields of Study & Subjects
Computability
Logic
AI Algorithms
Cellular Automata and Applications
Publication details
- Journal / source
- Logical Methods in Computer Science
- Publisher
- Centre pour la Communication Scientifique Directe (CCSD)
- Volume
- Volume 22, Issue 1
- Publication date
- 31 March 2026
- Language
- EN