Computability of Generalized Graphs

Computability of Generalized Graphs

We investigate conditions under which a semicomputable set is computable. In particular, we study topological pairs <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(<...

Full description

Saved in:
Bibliographic Details
Main Authors: Zvonko Iljazović, Matea Jelić
Format: Article
Language:English
Published: MDPI AG 2024-11-01
Series:Mathematics
Subjects:
computable topological space
computable type
topological graph
chainable graph
generalized graph
Online Access:https://www.mdpi.com/2227-7390/12/22/3468
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We investigate conditions under which a semicomputable set is computable. In particular, we study topological pairs <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(</mo><mi>A</mi><mo>,</mo><mi>B</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> which have a computable type, which means that in any computable topological space, a semicomputable set <i>S</i> is computable if there exists a semicomputable set <i>T</i> such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(</mo><mi>S</mi><mo>,</mo><mi>T</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> is homeomorphic to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(</mo><mi>A</mi><mo>,</mo><mi>B</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula>. It is known that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(</mo><mi>G</mi><mo>,</mo><mi>E</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> has a computable type if <i>G</i> is a topological graph and <i>E</i> is the set of all its endpoints. Furthermore, the same holds if <i>G</i> is a so-called chainable graph. We generalize the notion of a chainable graph and prove that the same result holds for a larger class of spaces.
ISSN:2227-7390

Similar Items