Graphs are not universal for online computability
From MaRDI portal
Publication:2186809
DOI10.1016/j.jcss.2020.02.004zbMath1476.03046OpenAlexW3011676745MaRDI QIDQ2186809
Alexander G. Melnikov, Matthew Harrison-Trainor, Rodney G. Downey, Iskander Sh. Kalimullin, Daniel D. 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
Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)
Related Items
Rogers semilattices of punctual numberings ⋮ Punctual copies of algebraic structures ⋮ Punctual 1-linear orders ⋮ Punctually presented structures I: Closure theorems ⋮ A structure of punctual dimension two ⋮ Online presentations of finitely generated structures ⋮ Punctual dimension of algebraic structures in certain classes ⋮ Punctual definability on structures ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Unnamed Item ⋮ PUNCTUAL CATEGORICITY AND UNIVERSALITY ⋮ A note on computable embeddings for ordinals and their reverses
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Independence in computable algebra
- Algebraic structures computable without delay
- Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
- Space complexity of abelian groups
- An on-line graph coloring algorithm with sublinear performance ratio
- Autostability of models
- Polynomial-time versus recursive models
- Polynomial-time Abelian groups
- On-line coloring \(k\)-colorable graphs
- Handbook of recursive mathematics. Vol. 2: Recursive algebra, analysis and combinatorics
- Combinatorial group theory.
- Degree spectra and computable dimensions in algebraic structures
- Structures computable in polynomial time. II
- The diversity of categoricity without delay
- Eliminating unbounded search in computable algebra
- The back-and-forth method and computability without delay
- Structures computable in polynomial time. I
- The additive group of the rationals does not have an automatic presentation
- Subgroups of finitely presented groups
- Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
- An Effective Version of Dilworth's Theorem
- Recursively Categorical Linear Orderings
- On-Line Coloring and Recursive Graph Theory
- A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS
- Degrees of Structures
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- CONSTRUCTIVE ALGEBRAS I
- Computable Algebra, General Theory and Theory of Computable Fields
- COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY
This page was built for publication: Graphs are not universal for online computability
