|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
On the Clones Containing a Near-Unanimity Functionстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Дата последнего поиска статьи во внешних источниках: 19 февраля 2018 г.
- Авторы: Zhuk D.N., Moiseev S.V.
- Сборник: Proceedings of the 2013 IEEE 43rd International Symposium on Multiple-Valued Logiс
- Год издания: 2013
- Издательство: Institute of Electrical and Electronics Engineers
- Местоположение издательства: Piscataway, NJ, United States
- Первая страница: 129
- Последняя страница: 134
- DOI: 10.1109/ISMVL.2013.46
- Аннотация: In previous papers we introduced the notion of an essential predicate, that is a predicate that cannot be presented as a conjunction of predicates with smaller arities. We showed that all clones of functions can be defined by a set of essential predicates. We introduced several operations on the set of essential predicates and defined a closure operator under these operations. There exists a one-to-one correspondence (a Galois connection) between clones and closed sets of essential predicates. Thus, these closed sets provide a valuable tool to studying clones. If the closure of a set of essential predicates is finite then it can be calculated using a computer. As it follows from Baker-Pixley theorem, a closed set corresponding to a clone is finite if and only if the clone contains a near-unanimity function. In the paper we present an approach to constructing a lattice of clones containing a given near-unanimity function. Particularly, all clones on three elements containing a majority function were calculated by a computer program. There turned out to be 1 918 040 clones. To analyze the possibility of constructing the lattices of clones in other cases, we give estimates on the number of clones containing a near-unanimity function of arity n. Also we prove estimates on the maximal size of a chain of clones containing a near-unanimity function. We conclude that it is impossible in practice to obtain the description for clones on four elements, as well as for a near-unanimity function of arity four.
- Добавил в систему: Жук Дмитрий Николаевич