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.

    https://doi.org/10.46298/lmcs-22(1:28)2026
    Source: arXiv.org:2411.13672
    Volume: Volume 22, Issue 1
    Published on: March 31, 2026
    Imported on: November 22, 2024
    Keywords: Logic in Computer Science, 03D78, 03D80, 03F60, F.1.1
    Licence: Attribution 4.0 International (CC BY 4.0)

    Share and export