Definable Subsets of Polynomial-Time Algebraic Structures

DOI10.1007/978-3-030-50026-9_10OpenAlexW3036808276MaRDI QIDQ5042236

Nikolay Bazhenov

Publication date: 19 October 2022

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-50026-9_10

zbMATH Keywords

Boolean algebracomputable structure theoryhereditarily finite superstructurelist structure\( \varDelta_0\) formula\( \varSigma \)-definabilitypolynomial-time structure

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraic structures computable without delay
• Arithmetic hierarchy and ideals of enumerated Boolean algebras
• Polynomial-time versus recursive models
• Generalized computability on real functions
• Polynomial-time Abelian groups
• Computable structures and the hyperarithmetical hierarchy
• On the complexity of formulas in semantic programming
• Structures computable in polynomial time. II
• Polynomial-time presentations of algebraic number fields
• Conditional terms in semantic programming
• Recursive terms in semantic programming
• Polynomial computability of fields of algebraic numbers
• Eliminating unbounded search in computable algebra
• The back-and-forth method and computability without delay
• The expressiveness of looping terms in the semantic programming
• Logical language of description of polynomial computing
• The uniformization problem for \(\Sigma\)-predicates in a hereditarily finite list superstructure over the real exponential field
• Structures computable in polynomial time. I
• The Boolean Algebra of Piecewise Testable Languages
• Effective procedures in field theory
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Σ-programming
• A construction for recursive linear orderings
• Boolean Algebras of Regular ω-Languages
• Computable Structure Theory
• Boolean Algebras of Regular Languages
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• CONSTRUCTIVE ALGEBRAS I
• Computable Algebra, General Theory and Theory of Computable Fields

This page was built for publication: Definable Subsets of Polynomial-Time Algebraic Structures