Volume 22, No 2, 2015, P. 49–62

UDC 519.716
S. S. Marchenkov
On the complexity of solving systems of functional equations in countable-valued logic

Abstract:
We propose a procedure to construct all solutions of an arbitrary system of functional equations in countable-valued logic. Based on this procedure, the solutions of systems of equations in the class $\Sigma_2$ of Kleene − Mostovsky arithmetical hierarchy which include only the ternary discriminator p are determined. We prove that for given systems of equations the components of solutions may be arbitrary functions of the class $\Sigma^1_1$ of Kleene analytical hierarchy.

Keywords: system of functional equations, function of countable-valued logic.

DOI: 10.17377/daio.2015.22.460

Sergey S. Marchenkov ¹
1. Moscow State University,
1 Leninskie gory, 119991 Moscow, Russia
e-mail: ssmarchen@yandex.ru

Received 2 September 2014
Revised 25 January 2015

References

[1] S. S. Marchenkov, Homogeneous algebras, in S. V. Yablonskii, ed., Problemy kibernetiki (Problems of Cybernetics), Vol. 39, pp. 85–106, Nauka, Moscow, 1982.

[2] S. S. Marchenkov, The closure operator in a multivalued logic based on functional equations, Diskretn. Anal. Issled. Oper., 17, No. 4, 18–31, 2010. Translated in J. Appl. Ind. Math., 5, No. 3, 383–390, 2011.

[3] S. S. Marchenkov, On classifications of many-valued logic functions by means of automorphism groups, Diskretn. Anal. Issled. Oper., 18, No. 4, 66–76, 2011.

[4] S. S. Marchenkov, FE-classification of functions of many-valued logic, Vestn. Mosk. Univ., Ser. 15, No. 2, 32–39, 2011. Translated in Mosc. Univ. Comput. Math. Cybern., 35, No. 2, 89–96, 2011.

[5] S. S. Marchenkov, Definability in the language of functional equations of a countable-valued logic, Diskretn. Mat., 25, No. 4, 13–23, 2013. Translated in Discrete Math. Appl., 23, No. 5–6, 451–462, 2013.

[6] S. S. Marchenkov and I. S. Kalinina, The FE-closure operator in countable-valued logic, Vestn. Mosk. Univ., Ser. 15, No. 3, 42–47, 2013. Translated in Mosc. Univ. Comput. Math. Cybern., 37, No. 3, 131–136, 2013.

[7] S. S. Marchenkov and V. S. Fedorova, On solutions to the systems of functional Boolean equations, Diskretn. Anal. Issled. Oper., 15, No. 6, 48–57, 2008. Translated in J. Appl. Ind. Math., 3, No. 4, 476–481, 2009.

[8] S. S. Marchenkov and V. S. Fedorova, On solutions to systems of functional equations of multiple-valued logic, Dokl. Akad. Nauk, 426, No. 4, 448–449, 2009. Translated in Dokl. Math., 79, No. 3, 382–383, 2009.

[9] S. S. Marchenkov and V. S. Fedorova, Solutions to the systems of functional equations of multivalued logic, Vestn. Mosk. Univ., Ser. 15, No. 4, 29–33, 2009. Translated in Mosc. Univ. Comput. Math. Cybern., 33, No. 4, 197–201, 2009.

[10] H. Rogers, Theory of Recursive Functions and Effective Computability, McGrow-Hill Book Co., New York, 1967. Translated under the title Teoriya rekursivnykh funktsii i effektivnaya vychislimost’, Mir, Moscow, 1972.