Eliminating unbounded search in computable algebra

DOI10.1007/978-3-319-58741-7_8zbMath1433.03117OpenAlexW2613792613MaRDI QIDQ2011637

Alexander G. Melnikov

Publication date: 4 August 2017

Full work available at URL: https://doi.org/10.1007/978-3-319-58741-7_8

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

New degree spectra of Polish spaces ⋮ Definable Subsets of Polynomial-Time Algebraic Structures ⋮ Rogers semilattices of punctual numberings ⋮ Primitive recursive equivalence relations and their primitive recursive complexity ⋮ Graphs are not universal for online computability ⋮ Primitive recursive reverse mathematics ⋮ A structure of punctual dimension two ⋮ Online presentations of finitely generated structures ⋮ The back-and-forth method and computability without delay ⋮ Punctual dimension of algebraic structures in certain classes ⋮ Punctual definability on structures ⋮ AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ On bi-embeddable categoricity of algebraic structures ⋮ PUNCTUAL CATEGORICITY AND UNIVERSALITY ⋮ Computable embeddability for algebraic structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Existence and uniqueness of structures computable in polynomial time
• Algebraic structures computable without delay
• Some constructivizations of Abelian groups
• 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
• A computability theoretic equivalent to Vaught's conjecture
• A survey of homogeneous structures
• 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))
• A computably categorical structure whose expansion by a constant has infinite computable dimension
• Automatic Structures: Richness and Limitations
• Finite Automata Presentable Abelian Groups
• The word problem

This page was built for publication: Eliminating unbounded search in computable algebra