FOUNDATIONS OF ONLINE STRUCTURE THEORY

DOI10.1017/bsl.2019.20zbMath1477.03167OpenAlexW2939890436WikidataQ128047871 ScholiaQ128047871MaRDI QIDQ5226592

Alexander G. Melnikov, Nikolay Bazhenov, Iskander Sh. Kalimullin, Rodney G. Downey

Publication date: 1 August 2019

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/cff7f0302b65f02c51b73f542f4ee8cd81a5fd0b

zbMATH Keywords

primitive recursiononline computationpunctual set theory

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Applications of computability and recursion theory (03D80) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Abstract and axiomatic computability and recursion theory (03D75)

Related Items

New degree spectra of Polish spaces, Constructing punctually categorical semigroups, Definable Subsets of Polynomial-Time Algebraic Structures, Primitive recursive ordered fields and some applications, Rogers semilattices of punctual numberings, Primitive recursive equivalence relations and their primitive recursive complexity, Punctual structures and primitive recursive reducibility, Graphs are not universal for online computability, Primitive recursive reverse mathematics, Punctual 1-linear orders, Effective categoricity of automatic equivalence and nested equivalence structures, On the main scientific achievements of Victor Selivanov, Punctually presented structures I: Closure theorems, A structure of punctual dimension two, COMPUTABLY COMPACT METRIC SPACES, Online presentations of finitely generated structures, Primitive recursive ordered fields and some applications, Punctual dimension of algebraic structures in certain classes, Punctual categoricity relative to a computable oracle, Punctual definability on structures, Non-density in punctual computability, Punctual categoricity spectra of computably categorical structures, On bi-embeddable categoricity of algebraic structures, Unnamed Item, PUNCTUAL CATEGORICITY AND UNIVERSALITY, To reorient is easier than to orient: An on-line algorithm for reorientation of graphs, A note on computable embeddings for ordinals and their reverses, Computable embeddability for algebraic structures, Searching for applicable versions of computable structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computable categoricity
• Algebraic structures computable without delay
• Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
• Some constructivizations of Abelian groups
• Space complexity of abelian groups
• An on-line graph coloring algorithm with sublinear performance ratio
• Computational complexity of real functions
• Polynomial-time versus recursive models
• Polynomial-time Abelian groups
• On-line coloring \(k\)-colorable graphs
• Handbook of recursive mathematics. Vol. 1: Recursive model theory
• Handbook of recursive mathematics. Vol. 2: Recursive algebra, analysis and combinatorics
• Computable structures and the hyperarithmetical hierarchy
• Structures computable in polynomial time. II
• The diversity of categoricity without delay
• Constructive models of complete solvable theories
• Eliminating unbounded search in computable algebra
• From automatic structures to automatic groups.
• Graphs are not universal for online computability
• A survey of homogeneous structures
• The back-and-forth method and computability without delay
• Structures computable in polynomial time. I
• Atomless Boolean algebras computable in polynomial time
• The additive group of the rationals does not have an automatic presentation
• Effective procedures in field theory
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Omitting types, type spectrums, and decidability
• Effective content of field theory
• An Effective Version of Dilworth's Theorem
• Recursively presentable prime models
• On-Line Coloring and Recursive Graph Theory
• A quest for algorithmically random infinite structures
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• CONSTRUCTIVE ALGEBRAS I
• Developments in Language Theory
• COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY