The present work considers the learning problem, i.e. the reconstruction or identification of a monotone function by its values at some points of its domain. The solution of this problem would allow to reduce the amount of brute force search in some applied problems. We demonstrate the existence of an optimal algorithm for learning monotone functions of finite-valued logic, that are defined on some domains. We also estimate the complexity of the optimal algorithm for each of the monotone function families under consideration.

monotone function learning, finite-valued logic, algorithm complexity, algebra of logic

Mathematical problems and theory of numerical methods