Definable Subsets of Polynomial-Time Algebraic Structures

DOI10.1007/978-3-030-50026-9_10MaRDI QIDQ5042236zbMATH OpenOpenAlexFDO

Authors 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

\( \varDelta_0\) formula\( \varSigma \)-definabilityBoolean algebracomputable structure theoryhereditarily finite superstructurelist structurepolynomial-time structure

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

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

Cited in

(8)

• Arithmetic complexity of first-order definable subsets of recursive Boolean algebras
• Light affine set theory: A naive set theory of polynomial time
• Structures computable in polynomial time. I
• Fixed-Point Definability and Polynomial Time
• Decidability of classes of algebraic systems in polynomial time
• Effective definability of Kolchin polynomials
• New algebraic invariants for definable subsets in universal algebra
• Punctual numberings for families of sets

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

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