The existence of a near-unanimity function is decidableстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 14 апреля 2015 г.
Аннотация:We prove that the following problem is decidable: given a finite set of relations on a finite set, decide whether this set admits a near-unanimity function. The proof is based on the upper bound on the minimal arity of a near-unanimity function admitted by a set of relations. Also, we give examples that show that the upper bound cannot be significantly improved.