The back-and-forth method and computability without delay

DOI10.1007/s11856-019-1948-5OpenAlexW2983092450WikidataQ126824153 ScholiaQ126824153MaRDI QIDQ2279959

Keng Meng Ng, Alexander G. Melnikov

Publication date: 17 December 2019

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11856-019-1948-5

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

Definable Subsets of Polynomial-Time Algebraic Structures, Rogers semilattices of punctual numberings, Graphs are not universal for online computability, Primitive recursive reverse mathematics, Effective categoricity of automatic equivalence and nested equivalence structures, A structure of punctual dimension two, Computable reducibility for computable linear orders of type \(\omega \), Online presentations of finitely generated structures, Punctual dimension of algebraic structures in certain classes, Non-density in punctual computability, FOUNDATIONS OF ONLINE STRUCTURE THEORY, Computable embeddability for algebraic structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Existence and uniqueness of structures computable in polynomial time
• Algebraic structures computable without delay
• 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 diversity of categoricity without delay
• Eliminating unbounded search in computable algebra
• A survey of homogeneous structures
• Atomless Boolean algebras computable in polynomial time
• The additive group of the rationals does not have an automatic presentation
• BREAKING UP FINITE AUTOMATA PRESENTABLE TORSION-FREE ABELIAN GROUPS
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Automatic Structures: Richness and Limitations
• CONSTRUCTIVE ALGEBRAS I
• Finite Automata Presentable Abelian Groups
• Computable Algebra, General Theory and Theory of Computable Fields
• Automatic presentations of structures