Rad HAZU, Matematičke znanosti, Vol. 29 (2025), 1-22.

COMPUTABILITY OF CHAINABLE GRAPHS

Zvonko Iljazović and Matea Jelić

Department of Mathematics, Faculty of Science, University of Zagreb, 10 000 Zagreb, Croatia
e-mail: zilj@math.hr

Faculty of Civil Engineering, Architecture and Geodesy, University of Split, 21 000 Split, Croatia
e-mail: matea.jelic@gradst.hr

Abstract.   If every semicomputable set, in arbitrary computable topological space, which is homeomorphic to a topological space A is computable, then we say that A has computable type. A topological pair (A, B), B ⊆ A, has computable type if for all semicomputable sets S and T, in arbitrary computable topological space, such that S is homeomorphic to A by a homeomorphism which maps T to B, it holds that S is computable. It is known that (G, E) has computable type, where G is a certain kind of topological graph and E is the set of its endpoints. In this paper, we consider more general graphs G~ obtained by taking edges of G~ to be chainable continua (instead of arcs) and we prove that (G~, E) has computable type, where E is the set of all endpoints of G~.

2020 Mathematics Subject Classification.   03D78, 03F60.

Key words and phrases.   Computable topological space, semicomputable set, computable set, computable type, chainable continuum, chainable graph.

Full text (PDF) (free access)

DOI: https://doi.org/10.21857/y6zolb4zom

References:

  1. D. E. Amir and M. Hoyrup, Computability of finite simplicial complexes, in: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) (eds. M. Bojańczyk et al.), Art. No. 111, 16 pp, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022.
    MathSciNet     CrossRef

  2. V. Brattka, Plottable real number functions and the computable graph theorem, SIAM J. Comput. 38 (2008), 303-328.
    MathSciNet     CrossRef

  3. V. Brattka and G. Presser, Computability on subsets of metric spaces, Theoret. Comput. Sci. 305 (2003), 43-76.
    MathSciNet     CrossRef

  4. V. Brattka and K. Weihrauch, Computability on subsets of Euclidean space I. Closed and compact subsets, Theoret. Comput. Sci. 219 (1999), 65-93.
    MathSciNet     CrossRef

  5. C. E. Burgess, Chainable continua and indecomposability, Pacific J. Math. 9 (1959), 653-659.
    MathSciNet     CrossRef

  6. K. Burnik and Z. Iljazović, Computability of 1-manifolds, Log. Methods Comput. Sci. 10 (2014), no. 2, (2:8), 28 pp.
    MathSciNet     CrossRef

  7. V. Čačić, M. Horvat and Z. Iljazović, Computable subcontinua of semicomputable chainable Hausdorff continua, Theoret. Comput. Sci. 892 (2021), 155-169.
    MathSciNet     CrossRef

  8. M. Čelar and Z. Iljazović, Computability of products of chainable continua, Theory Comput. Syst. 65 (2021), 410-427.
    MathSciNet     CrossRef

  9. M. Čelar and Z. Iljazović, Computability of glued manifolds, J. Logic Comput. 32 (2022), 65-97.
    MathSciNet     CrossRef

  10. E. Čičković, Z. Iljazović and L. Validžić, Chainable and circularly chainable semicomputable sets in computable topological spaces, Arch. Math. Logic 58 (2019), 885-897.
    MathSciNet     CrossRef

  11. M. Horvat, Z. Iljazović and B. Pažek, Computability of pseudo-cubes, Ann. Pure Appl. Logic 171 (2020), no. 8, 102823, 21 pp.
    MathSciNet     CrossRef

  12. Z. Iljazović, Chainable and circularly chainable co-r.e. sets in computable metric spaces, J. UCS 15 (2009), 1206-1235.
    MathSciNet

  13. Z. Iljazović, Co-c.e. spheres and cells in computable metric spaces, Log. Methods Comput. Sci. 7 (2011), no. 3, 3:05, 21 pp.
    MathSciNet     CrossRef

  14. Z. Iljazović, Compact manifolds with computable boundaries, Log. Methods Comput. Sci. 9 (2013), no. 4, 4:19, 22 pp.
    MathSciNet     CrossRef

  15. Z. Iljazović, Computability of graphs, MLQ Math. Log. Q. 66 (2020), 51-64.
    MathSciNet     CrossRef

  16. Z. Iljazović and B. Pažek, Computable intersection points, Computability 7 (2018), 57-99.
    MathSciNet     CrossRef

  17. Z. Iljazović and B. Pažek, Warsaw discs and semicomputability, Topology Appl. 239 (2018), 308-323.
    MathSciNet     CrossRef

  18. Z. Iljazović and I. Sušić, Semicomputable manifolds in computable topological spaces, J. Complexity 45 (2018), 83-114.
    MathSciNet     CrossRef

  19. T. Kihara, Incomputability of simply connected planar continua, Computability 1(2) (2012), 131-152.
    MathSciNet     CrossRef

  20. J. S. Miller, Effectiveness for embedded spheres and balls, Electronic Notes in Theoretical Computer Science 66 (2002), 127-138.
    CrossRef

  21. M. B. Pour-El and J. I. Richards, Computability in Analysis and Physics, Springer-Verlag, Berlin, 1989.
    MathSciNet     CrossRef

  22. E. Specker, Der satz vom maximum in der rekursiven analysis, in: Constructivity in Mathematics (ed. A. Heyting), North Holland Publ. Comp., Amsterdam, 1959, pp. 254-265.
    MathSciNet

  23. H. Tanaka, On a Π01 set of positive measure, Nagoya Math. J. 38 (1970), 139-144.
    MathSciNet

  24. A. M. Turing, On computable numbers, with an application to the entscheidungsproblem, Proc. London Math. Soc. (2) 42 (1936), 230-265.
    MathSciNet     CrossRef

  25. K. Weihrauch, Computability on computable metric spaces, Theoret. Comput. Sci. 113 (1993), 191-210.
    MathSciNet     CrossRef

  26. K. Weihrauch, Computable Analysis, Springer-Verlag, Berlin, 2000.
    MathSciNet     CrossRef

  27. K. Weihrauch, Computable separation in topology, from T0 to T2, J.UCS 16 (2010), 2733-2753.
    MathSciNet

  28. K. Weihrauch and T. Grubba, Elementary computable topology, J.UCS 15 (2009), 1381-1422.
    MathSciNet

Rad HAZU Home Page