Constructing Decidable Graphs from Decidable Structures

N. A. Bazhenov; M. Harrison-Trainor

doi:10.1007/s10469-019-09558-8

Constructing Decidable Graphs from Decidable Structures

N. A. Bazhenov, M. Harrison-Trainor

Кафедра дискретной математики и информатики ММФ и СУНЦ

Результат исследования: Научные публикации в периодических изданиях › статья

Аннотация

It is shown that every structure (including one in an infinite language) can be transformed into a graph that is bi-interpretable with the original structure, for which the full elementary diagrams can be computed one from the other.

Язык оригинала	английский
Страницы (с-по)	369-382
Число страниц	14
Журнал	Algebra and Logic
Том	58
Номер выпуска	5
DOI	https://doi.org/10.1007/s10469-019-09558-8
Состояние	Опубликовано - 1 ноя 2019

ГРНТИ

27 МАТЕМАТИКА

Доступ к документу

10.1007/s10469-019-09558-8

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «Constructing Decidable Graphs from Decidable Structures». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@article{ce44859625564685858f992d9f00aef1,

title = "Constructing Decidable Graphs from Decidable Structures",

abstract = "It is shown that every structure (including one in an infinite language) can be transformed into a graph that is bi-interpretable with the original structure, for which the full elementary diagrams can be computed one from the other.",

keywords = "bi-interpretable structures, decidable graph, decidable structure, full diagram, DEGREE SPECTRA",

author = "Bazhenov, {N. A.} and M. Harrison-Trainor",

year = "2019",

month = nov,

day = "1",

doi = "10.1007/s10469-019-09558-8",

language = "English",

volume = "58",

pages = "369--382",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer US",

number = "5",

}

TY - JOUR

T1 - Constructing Decidable Graphs from Decidable Structures

AU - Bazhenov, N. A.

AU - Harrison-Trainor, M.

PY - 2019/11/1

Y1 - 2019/11/1

N2 - It is shown that every structure (including one in an infinite language) can be transformed into a graph that is bi-interpretable with the original structure, for which the full elementary diagrams can be computed one from the other.

AB - It is shown that every structure (including one in an infinite language) can be transformed into a graph that is bi-interpretable with the original structure, for which the full elementary diagrams can be computed one from the other.

KW - bi-interpretable structures

KW - decidable graph

KW - decidable structure

KW - full diagram

KW - DEGREE SPECTRA

UR - http://www.scopus.com/inward/record.url?scp=85076014888&partnerID=8YFLogxK

U2 - 10.1007/s10469-019-09558-8

DO - 10.1007/s10469-019-09558-8

M3 - Article

AN - SCOPUS:85076014888

VL - 58

SP - 369

EP - 382

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 5

ER -