On Categoricity Spectra for Locally Finite Graphs Full article
| Journal |
Siberian Mathematical Journal
ISSN: 0037-4466 , E-ISSN: 1573-9260 |
||
|---|---|---|---|
| Output data | Year: 2021, Volume: 62, Number: 5, Pages: 796-804 Pages count : 9 DOI: 10.1134/S0037446621050037 | ||
| Tags | 510.5; autostability; categoricity spectrum; computable categoricity; computable model; degree of categoricity; locally finite graph | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Foundation for Basic Research | 20-31-70006 |
Abstract:
Under study is the algorithmic complexity of isomorphisms between computable copiesof locally finite graphs $ G $ (undirected graphs whose every vertex has finite degree).We obtain the following results: If $ G $ has only finitely many components then $ G $is $ {\mathbf{d}} $-computably categorical for every Turing degree $ {\mathbf{d}} $from the class $ PA({\mathbf{0}}^{\prime}) $. If $ G $ has infinitely many components then $ G $is $ {\mathbf{0}}^{\prime\prime} $-computably categorical. We exhibit a series of examplesshowing that the obtained bounds are sharp. © 2021, Pleiades Publishing, Ltd.
Cite:
Bazhenov N.A.
, Marchuk M.I.
On Categoricity Spectra for Locally Finite Graphs
Siberian Mathematical Journal. 2021. V.62. N5. P.796-804. DOI: 10.1134/S0037446621050037 WOS Scopus OpenAlex
On Categoricity Spectra for Locally Finite Graphs
Siberian Mathematical Journal. 2021. V.62. N5. P.796-804. DOI: 10.1134/S0037446621050037 WOS Scopus OpenAlex
Identifiers:
| Web of science: | WOS:000698762500003 |
| Scopus: | 2-s2.0-85115628413 |
| OpenAlex: | W3204193042 |
Citing:
Пока нет цитирований