Naslov
Computability of graphs

Autori
Iljazović, Zvonko

Izvornik
Mathematical logic quarterly (0942-5616) 66 (2020), 1; 51-64

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Computable topological space ; Computable set ; Semicomputable set ; Graph

Sažetak
We consider topological pairs $(A , B )$, $B\subseteq A$, which have computable type, which means that they have the following property: if $X$ is a computable topological space and $f:A\rightarrow X$ a topological imbedding such that $f(A )$ and $f(B )$ are semicomputable sets in $X$, then $f(A )$ is a computable set in $X$. It is known for example that $(M, \partial M)$ has computable type if $M$ is a compact manifold with boundary. In this paper we examine topological spaces called graphs and we show that we can in a natural way associate to each graph $G$ a discrete subspace $E$ so that $(G, E)$ has computable type. Furthermore, we use this result to conclude that certain noncompact semicomputable graphs in computable metric spaces are computable.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA