On complexity of problem of satisfiability for systems of countable-valued functional equations

DOI10.3103/S1066369X15080034MaRDI QIDQ905075zbMATH OpenOpenAlexFDO

Authors I. S. Kalinina, S. S. Marchenkov

Publication date 14 January 2016

Published in Russian Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/s1066369x15080034

zbMATH Keywords

countable-valued logicKleene-Mostowski arithmetical hierarchyproblem of satisfiabilitysystem of functional equations

Mathematics Subject Classification ID

Functional equations for complex functions (39B32) Systems of functional equations and inequalities (39B72)

Review text

The authors prove that the problem of satisfiability for the system of functional equations over the set \(\{ p\}\) belongs to the class \(\prod_1 \) of Kleene-Mostowski arithmetical hierarchy. As a result, they show that the set of all satisfiable systems of functional equations over \(\{ p\}\) is an \(m\)-complete set in the class \(\prod_1 \) of the Kleene-Mostowski hierarchy.

Recommendations

• On the complexity of solutions of systems of functional equations in countable-valued logic
• On the complexity of the satisfiability problem for a system of functional Boolean equations
• scientific article; zbMATH DE number 1943080
• On solutions to systems of automata-type functional equations
• Complexity of generalized satisfiability counting problems

Cites work

• Definability in the language of functional equations of a countable-valued logic
• Equational characterizations of Boolean function classes
• Equational classes of Boolean functions via the HSP theorem
• FE classification of functions of many-valued logic
• Galois theory for minors of finite functions
• scientific article; zbMATH DE number 6004972 (Why is no real title available?)
• scientific article; zbMATH DE number 3819803 (Why is no real title available?)
• On classifications of many-valued logic functions by means of automorphism groups
• On solutions to systems of functional equations of multiple-valued logic
• On the complexity of the satisfiability problem for a system of functional Boolean equations
• Solutions to the systems of functional equations of multivalued logic
• The closure operator in a multi-valued logic based on functional equations
• The FE-closure operator in countable-valued logic
• The ternary discriminator function in universal algebra

Cited in

(6)

• Functional equations for the functions of real variables
• On the complexity of solutions of systems of functional equations in countable-valued logic
• On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations
• scientific article; zbMATH DE number 1943080 (Why is no real title available?)
• On solutions to systems of automata-type functional equations
• On the complexity of the satisfiability problem for a system of functional Boolean equations

This page was built for publication: On complexity of problem of satisfiability for systems of countable-valued functional equations

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