Constructing decidable graphs from decidable structures

DOI10.1007/S10469-019-09558-8MaRDI QIDQ2300933zbMATH OpenOpenAlexFDO

Authors Matthew Harrison-Trainor, Nikolay Bazhenov

Publication date 28 February 2020

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10469-019-09558-8

zbMATH Keywords

decidable structurebi-interpretable structuresdecidable graphfull diagram

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Recommendations

• Nonmaximal decidable structures
• scientific article; zbMATH DE number 18951
• Automatic Structures of Bounded Degree Revisited
• When Is Reachability Intrinsically Decidable?
• Transforming structures by set interpretations

Cites work

• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 934359 (Why is no real title available?)
• A computable functor from graphs to fields
• A computable ℵ₀-categorical structure whose theory computes true arithmetic
• A fixed point for the jump operator on structures
• An autostable 1-decidable model without a computable Scott family of \(\exists\)-formulas
• Autostability and computable families of constructivizations
• Computability theoretic classifications for classes of structures
• Computable trees, prime models, and relative decidability
• Degree spectra and computable dimensions in algebraic structures
• Degree spectra of structures relative to equivalences
• Enumerations, countable structures and Turing degrees
• Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations
• Problem of the number of non-self-equivalent constructivizations
• Relative to any nonrecursive set
• Spectra of theories and structures
• The quantity of nonautoequivalent constructivizations
• Theory spectra and classes of theories
• There is no classification of the decidably presentable structures

Cited in

(5)

• A note on decidable categoricity and index sets
• Decidability of string graphs
• scientific article; zbMATH DE number 56048 (Why is no real title available?)
• Nonmaximal decidable structures
• scientific article; zbMATH DE number 5030273 (Why is no real title available?)

This page was built for publication: Constructing decidable graphs from decidable structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300933)