On algorithmic solvability of the A-completeness problem for systems of boundedly determinate functions containing all one-place boundedly determinate S-functions

DOI10.1515/DMA-2012-038MaRDI QIDQ5299971zbMATH OpenOpenAlexFDO

Authors V. A. Buevich, M. A. Podkolzina

Publication date 24 June 2013

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma-2012-038

zbMATH Keywords

\(A\)-completeness\(A\)-precompletenessboundedly determinate

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• On the existence of an algorithm for recognizing the A-completeness of systems containing all one-place bounded-determinate functions.
• On completeness and A-completeness of S-sets of determinate functions containing all one-place determinate S-functions
• scientific article; zbMATH DE number 3898772
• Undecidability of the completeness and A-completeness problems for some systems of automaton functions
• scientific article; zbMATH DE number 2032360

Cited in

(6)

• A problem of completeness of S-sets of deterministic functions
• On completeness and A-completeness of S-sets of determinate functions containing all one-place determinate S-functions
• AN ELEMENTARY SYSTEM AS AND ITS SEMI‐COMPLETENESS AND DECIDABILITY
• A criterion of completeness for non-homogeneous functions with delays
• On the existence of an algorithm for recognizing the A-completeness of systems containing all one-place bounded-determinate functions.
• The completeness problem in the class of polynomials is resolvable

This page was built for publication: On algorithmic solvability of the \(A\)-completeness problem for systems of boundedly determinate functions containing all one-place boundedly determinate \(S\)-functions

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