Graphs are not universal for online computability

DOI10.1016/J.JCSS.2020.02.004MaRDI QIDQ2186809zbMATH OpenOpenAlexFDO

Authors Matthew Harrison-Trainor, Alexander Melnikov, Rodney G. Downey, Iskander Kalimullin, Daniel Turetsky

Publication date 9 June 2020

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2020.02.004

zbMATH Keywords

logiccomputabilityabstract theory of online computation

Mathematics Subject Classification ID

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

Recommendations

• Graph representation functions computable by finite automata
• Computable Categoricity of Graphs with Finite Components
• PUNCTUAL CATEGORICITY AND UNIVERSALITY
• A computable functor from graphs to fields
• Computable isomorphisms for certain classes of infinite graphs

Cites work

• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1302869 (Why is no real title available?)
• scientific article; zbMATH DE number 1302879 (Why is no real title available?)
• scientific article; zbMATH DE number 1303205 (Why is no real title available?)
• scientific article; zbMATH DE number 2040323 (Why is no real title available?)
• scientific article; zbMATH DE number 2047478 (Why is no real title available?)
• scientific article; zbMATH DE number 1499098 (Why is no real title available?)
• scientific article; zbMATH DE number 1421070 (Why is no real title available?)
• scientific article; zbMATH DE number 1450824 (Why is no real title available?)
• A computable functor from graphs to fields
• Algebraic structures computable without delay
• An Effective Version of Dilworth's Theorem
• An on-line graph coloring algorithm with sublinear performance ratio
• Autostability of models
• CONSTRUCTIVE ALGEBRAS I
• Combinatorial group theory.
• Computable Algebra, General Theory and Theory of Computable Fields
• Computable functors and effective interpretability
• Degree spectra and computable dimensions in algebraic structures
• Degrees of Structures
• Eliminating unbounded search in computable algebra
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
• Handbook of recursive mathematics. Vol. 2: Recursive algebra, analysis and combinatorics
• Independence in computable algebra
• On-Line Coloring and Recursive Graph Theory
• On-line coloring \(k\)-colorable graphs
• Polynomial-time Abelian groups
• Polynomial-time versus recursive models
• Recursively Categorical Linear Orderings
• Space complexity of abelian groups
• Structures computable in polynomial time. I
• Structures computable in polynomial time. II
• Subgroups of finitely presented groups
• The additive group of the rationals does not have an automatic presentation
• The back-and-forth method and computability without delay
• The diversity of categoricity without delay

Cited in

(14)

• A structure of punctual dimension two
• PUNCTUAL CATEGORICITY AND UNIVERSALITY
• Punctually presented structures I: Closure theorems
• A computable functor from graphs to fields
• Punctual dimension of algebraic structures in certain classes
• Punctual 1-linear orders
• Punctual copies of algebraic structures
• Online presentations of finitely generated structures
• Punctual definability on structures
• Online, computable and punctual structure theory
• Rogers semilattices of punctual numberings
• A note on computable embeddings for ordinals and their reverses
• scientific article; zbMATH DE number 7407778 (Why is no real title available?)
• FOUNDATIONS OF ONLINE STRUCTURE THEORY

This page was built for publication: Graphs are not universal for online computability

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