Online presentations of finitely generated structures

DOI10.1016/J.TCS.2020.08.021MaRDI QIDQ2205949zbMATH OpenOpenAlexFDO

Authors Alexander Melnikov, Keng Meng Ng, Nikolay Bazhenov, Iskander Kalimullin

Publication date 21 October 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.08.021

zbMATH Keywords

finitely generated structureisomorphismprimitive recursive function

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Other Turing degree structures (03D28) Theory of numerations, effectively presented structures (03D45) Online algorithms; streaming algorithms (68W27)

Recommendations

• Degrees of presentability of structures. I
• A structure of punctual dimension two
• Punctual copies of algebraic structures
• Structures computable in polynomial time. I
• Degree Structures: Local and Global Investigations

Cites work

• A note on finite ring extensions
• Algebraic structures computable without delay
• An Effective Version of Dilworth's Theorem
• An on-line graph coloring algorithm with sublinear performance ratio
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Categoricity for primitive recursive and polynomial Boolean algebras
• Combinatorial group theory.
• Computable Algebra, General Theory and Theory of Computable Fields
• Computable structures and the hyperarithmetical hierarchy
• Elementary theory of a finitely generated commutative ring
• Eliminating unbounded search in computable algebra
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• Golod-Shafarevich groups: a survey.
• Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
• Graphs are not universal for online computability
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• scientific article; zbMATH DE number 5605134 (Why is no real title available?)
• scientific article; zbMATH DE number 3781440 (Why is no real title available?)
• scientific article; zbMATH DE number 1302879 (Why is no real title available?)
• scientific article; zbMATH DE number 1303204 (Why is no real title available?)
• scientific article; zbMATH DE number 1499098 (Why is no real title available?)
• scientific article; zbMATH DE number 1450824 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• On-line coloring \(k\)-colorable graphs
• On-Line Coloring and Recursive Graph Theory
• Polynomial-time versus recursive models
• Primitively recursively categorical linear orderings
• Structures computable in polynomial time. I
• Structures computable in polynomial time. II
• Subgroups of finitely presented groups
• Subrings of finite index in finitely generated rings
• The back-and-forth method and computability without delay
• The diversity of categoricity without delay
• The logical complexity of finitely generated commutative rings
• Three lectures on automatic structures

Cited in

(11)

• Punctual dimension of algebraic structures in certain classes
• Non-density in punctual computability
• Punctual categoricity spectra of computably categorical structures
• Primitive recursive equivalence relations and their primitive recursive complexity
• Punctually presented structures I: Closure theorems
• A pathological punctually 1-decidable structure
• A discrete linear order with non-dense punctual degrees
• Punctually presented structures. II: Comparing presentations.
• Structures of finite punctual dimension \(n>2\)
• Punctual presentability in certain classes of algebraic structures
• Punctual numberings for families of sets

This page was built for publication: Online presentations of finitely generated structures

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