Algebraic structures computable without delay

DOI10.1016/J.TCS.2017.01.029zbMath1418.03151OpenAlexW2594352983MaRDI QIDQ528478

Keng Meng Ng, Iskander Sh. Kalimullin, Alexander G. Melnikov

Publication date: 12 May 2017

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

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

zbMATH Keywords

primitive recursionautomatic algebrapolynomial structures

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45)

Related Items (40)

New degree spectra of Polish spaces ⋮ Constructing punctually categorical semigroups ⋮ Definable Subsets of Polynomial-Time Algebraic Structures ⋮ Rogers semilattices of punctual numberings ⋮ Primitive recursive equivalence relations and their primitive recursive complexity ⋮ Structures computable in polynomial time. I ⋮ Punctual structures and primitive recursive reducibility ⋮ Punctual copies of algebraic structures ⋮ Graphs are not universal for online computability ⋮ Primitive recursive reverse mathematics ⋮ Punctual 1-linear orders ⋮ The diversity of categoricity without delay ⋮ On the main scientific achievements of Victor Selivanov ⋮ Inversion operations in algebraic structures ⋮ Punctually presented structures I: Closure theorems ⋮ A structure of punctual dimension two ⋮ Computable reducibility for computable linear orders of type \(\omega \) ⋮ The complexity of inversion in groups ⋮ Online presentations of finitely generated structures ⋮ Categoricity for primitive recursive and polynomial Boolean algebras ⋮ Primitively recursively categorical linear orderings ⋮ Primitive recursive fields and categoricity ⋮ Eliminating unbounded search in computable algebra ⋮ The back-and-forth method and computability without delay ⋮ Punctual dimension of algebraic structures in certain classes ⋮ Punctual categoricity relative to a computable oracle ⋮ Punctual definability on structures ⋮ On the index set of punctually categorical finitely generated structures ⋮ AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES ⋮ Non-density in punctual computability ⋮ Computably and punctually universal spaces ⋮ Primitively recursive categoricity for unars and equivalence structures ⋮ Punctual categoricity spectra of computably categorical structures ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Finitely generated structures computable in polynomial time ⋮ Unnamed Item ⋮ Quotient structures and groups computable in polynomial time ⋮ PUNCTUAL CATEGORICITY AND UNIVERSALITY ⋮ Computable embeddability for algebraic structures ⋮ Searching for applicable versions of computable structures

Cites Work

• Existence and uniqueness of structures computable in polynomial time
• Independence in computable algebra
• FA-presentable groups and rings
• Space complexity of abelian groups
• Polynomial-time versus recursive models
• Polynomial-time Abelian groups
• Computable structures and the hyperarithmetical hierarchy
• The computable dimension of ordered abelian groups
• Degrees of categoricity of computable structures
• COMPUTABLE ABELIAN GROUPS
• Computably Categorical Fields via Fermat’s Last Theorem
• An introduction to computable model theory on groups and fields
• DECIDABLE MODELS OF ω-STABLE THEORIES
• The additive group of the rationals does not have an automatic presentation
• BREAKING UP FINITE AUTOMATA PRESENTABLE TORSION-FREE ABELIAN GROUPS
• Subgroups of finitely presented groups
• Recursive Boolean algebras with recursive atoms
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Recursively presentable prime models
• Relative to any nonrecursive set
• Enumerations, countable structures and Turing degrees
• A computably categorical structure whose expansion by a constant has infinite computable dimension
• Automatic Structures: Richness and Limitations
• CONSTRUCTIVE ALGEBRAS I
• Finite Automata Presentable Abelian Groups
• Computable Algebra, General Theory and Theory of Computable Fields
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algebraic structures computable without delay