Graphs are not universal for online computability
The authors study the so-called punctually universal classes of structures. Informally, a class of structures is called punctually universal if there is a uniform primitive recursive transformation that transforms any structure of finite signature into a structure in that class, and that this transformation has an inverse transformation, and both transformations also respect isomorphisms. They prove that the class of structures with only one binary function symbol is punctually universal. A description of punctually categorical graphs is given. It follows from this description that the class of graphs is not punctually universal.
- 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
- Combinatorial group theory.
- Computable Algebra, General Theory and Theory of Computable Fields
- Computable functors and effective interpretability
- CONSTRUCTIVE ALGEBRAS I
- 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
- 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?)
- Independence in computable algebra
- On-line coloring \(k\)-colorable graphs
- On-Line Coloring and Recursive Graph Theory
- 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
- Punctual dimension of algebraic structures in certain classes
- Punctual definability on structures
- A note on computable embeddings for ordinals and their reverses
- Punctual copies of algebraic structures
- Online presentations of finitely generated structures
- A computable functor from graphs to fields
- Rogers semilattices of punctual numberings
- A structure of punctual dimension two
- Foundations of online structure theory. II: The operator approach
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- PUNCTUAL CATEGORICITY AND UNIVERSALITY
- Punctual 1-linear orders
- Punctually presented structures I: Closure theorems
- Online, computable and punctual structure theory
- A pathological punctually 1-decidable structure
- A discrete linear order with non-dense punctual degrees
- Punctually presented structures. II: Comparing presentations.
- Punctual numberings for families of sets
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)
