Polynomial-time algorithms for verification of some properties ofk-valued functions represented by polynomials

摘要

The aim of this paper is to present a general approach todesigning efficient algorithms intended for checking some properties(monotonicity, some specific variants of precompleteness, etc.) ofmultiple-valued functions represented by polynomials. The propertiesunder consideration are characterized by predicates. The key idea ofthis approach is based upon the extension of the concept of transitivityto predicates of arbitrary arity. We demonstrate that whenevermultiple-valued functions are represented by polynomials and some set offunctions is characterized by an extended transitive and total reflexivepredicate, then the membership problem for this class is decidable inpolynomial time