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

Section of Discrete Mathematics and Computer Science

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

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.

Original language	English
Pages (from-to)	369-382
Number of pages	14
Journal	Algebra and Logic
Volume	58
Issue number	5
DOIs	https://doi.org/10.1007/s10469-019-09558-8
Publication status	Published - 1 Nov 2019

Keywords

bi-interpretable structures
decidable graph
decidable structure
full diagram
DEGREE SPECTRA

State classification of scientific and technological information

27 MATHEMATICS

Access to Document

10.1007/s10469-019-09558-8

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Constructing Decidable Graphs from Decidable Structures'. Together they form a unique fingerprint.

Cite this

@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 -