Vedran Čačić ; Matea Čelar ; Marko Horvat ; Zvonko Iljazović - Computable Approximations of Semicomputable Graphs

lmcs:14835 - Logical Methods in Computer Science, March 31, 2026, Volume 22, Issue 1 - https://doi.org/10.46298/lmcs-22(1:28)2026
Computable Approximations of Semicomputable GraphsArticle

Authors: Vedran Čačić ; Matea Čelar ; Marko Horvat ; Zvonko Iljazović

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.


Volume: Volume 22, Issue 1
Published on: March 31, 2026
Accepted on: February 9, 2026
Submitted on: November 22, 2024
Keywords: Logic in Computer Science, 03D78, 03D80, 03F60, F.1.1

Consultation statistics

This page has been seen 132 times.
This article's PDF has been downloaded 42 times.