Logical language of description of polynomial computing

DOI10.1134/S1064562419020030MaRDI QIDQ2313239zbMATH OpenOpenAlexFDO

Authors D. I. Sviridenko, S. S. Goncharov

Publication date 18 July 2019

Published in Doklady Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s1064562419020030

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On the complexity of formulas in semantic programming
• Towards a calculus of algorithms
• On the polynomial computability of some rudimentary predicates.
• A logic for constant-depth circuits
• Polynomial queries to relational data bases

Cites work

• scientific article; zbMATH DE number 3980456 (Why is no real title available?)
• scientific article; zbMATH DE number 4021108 (Why is no real title available?)
• scientific article; zbMATH DE number 4047058 (Why is no real title available?)
• scientific article; zbMATH DE number 3494394 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 890268 (Why is no real title available?)
• Computational Complexity
• Conditional terms in semantic programming
• On the complexity of formulas in semantic programming

Cited in

(5)

• The expressiveness of looping terms in the semantic programming
• Semantic programming and polynomially computable representations
• Definable Subsets of Polynomial-Time Algebraic Structures
• Some questions on polynomially computable representations for generating grammars and Backus-Naur forms
• scientific article; zbMATH DE number 3852958 (Why is no real title available?)

This page was built for publication: Logical language of description of polynomial computing

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