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

I. S. Kalinina, S. S. Marchenkov

Chair of Mathematical Cybernetics, Moscow State University, 1 Leninskie Gory, Bld. 52, GSP-1, Moscow, 119991 Russia

Abstract: We consider the problem of satisfiability for systems of countable-valued functional equations, containing ternary discriminator function $p$. We prove that this problem is $m$-complete in the class $\Pi_1$ of Kleene–Mostovsky's hierarchy.

Keywords: functional equations, countable-valued logic, problem of satisfiability.

UDC: 519.716

Received: 06.06.2014

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2015, 59:8, 19–24

Bibliographic databases:

•