Graphs are not universal for online computability
DOI10.1016/J.JCSS.2020.02.004zbMATH Open1476.03046OpenAlexW3011676745MaRDI QIDQ2186809FDOQ2186809
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
Recommendations
Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)
Cites Work
- Title not available (Why is that?)
- The additive group of the rationals does not have an automatic presentation
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Effective Version of Dilworth's Theorem
- Autostability of models
- Subgroups of finitely presented groups
- Recursively Categorical Linear Orderings
- Title not available (Why is that?)
- On-line coloring \(k\)-colorable graphs
- Combinatorial group theory.
- CONSTRUCTIVE ALGEBRAS I
- Computable Algebra, General Theory and Theory of Computable Fields
- Polynomial-time versus recursive models
- Polynomial-time Abelian groups
- Title not available (Why is that?)
- On-Line Coloring and Recursive Graph Theory
- An on-line graph coloring algorithm with sublinear performance ratio
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
- Title not available (Why is that?)
- Degree spectra and computable dimensions in algebraic structures
- Degrees of Structures
- Independence in computable algebra
- A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS
- Space complexity of abelian groups
- Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
- Title not available (Why is that?)
- Algebraic structures computable without delay
- Title not available (Why is that?)
- Handbook of recursive mathematics. Vol. 2: Recursive algebra, analysis and combinatorics
- Structures computable in polynomial time. I
- Eliminating unbounded search in computable algebra
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- Structures computable in polynomial time. II
- The diversity of categoricity without delay
- COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY
- The back-and-forth method and computability without delay
Cited In (12)
- PUNCTUAL CATEGORICITY AND UNIVERSALITY
- Punctually presented structures I: Closure theorems
- 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
- Rogers semilattices of punctual numberings
- A note on computable embeddings for ordinals and their reverses
- Title not available (Why is that?)
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- A structure of punctual dimension two
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)
