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">(<...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-11-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/22/3468 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850227122246778880 |
|---|---|
| author | Zvonko Iljazović Matea Jelić |
| author_facet | Zvonko Iljazović Matea Jelić |
| author_sort | Zvonko Iljazović |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-7571dfc84426447e81efc6879f103cb7 |
| institution | OA Journals |
| issn | 2227-7390 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-7571dfc84426447e81efc6879f103cb72025-08-20T02:04:54ZengMDPI AGMathematics2227-73902024-11-011222346810.3390/math12223468Computability of Generalized GraphsZvonko Iljazović0Matea Jelić1Faculty of Science, University of Zagreb, 10000 Zagreb, CroatiaFaculty of Civil Engineering, Architecture and Geodesy, University of Split, 21000 Split, CroatiaWe 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.https://www.mdpi.com/2227-7390/12/22/3468computable topological spacecomputable typetopological graphchainable graphgeneralized graph |
| spellingShingle | Zvonko Iljazović Matea Jelić Computability of Generalized Graphs Mathematics computable topological space computable type topological graph chainable graph generalized graph |
| title | Computability of Generalized Graphs |
| title_full | Computability of Generalized Graphs |
| title_fullStr | Computability of Generalized Graphs |
| title_full_unstemmed | Computability of Generalized Graphs |
| title_short | Computability of Generalized Graphs |
| title_sort | computability of generalized graphs |
| topic | computable topological space computable type topological graph chainable graph generalized graph |
| url | https://www.mdpi.com/2227-7390/12/22/3468 |
| work_keys_str_mv | AT zvonkoiljazovic computabilityofgeneralizedgraphs AT mateajelic computabilityofgeneralizedgraphs |