• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 5
Sort:
by name
by year
Article
Yashunsky A. Algebra Universalis. 2019. Vol. 80. No. 1 (5). P. 1-16.

We consider the problem of approximating distributions of Bernoulli random variables by applying Boolean functions to independent random variables with distributions from a given set. For a set B of Boolean functions, the set of approximable distributions forms an algebra, named the approximation algebra of Bernoulli distributions induced by B. We provide a complete description of approximation algebras induced by most clones of Boolean functions. For remaining clones, we prove a criterion for approximation algebras and a property of algebras that are finitely generated.

Added: Sep 9, 2020
Article
Kazda A., Zhuk D. Algebra Universalis. 2021. Vol. 82.

We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at most N, where the number N depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on N that, in the special case of algebras with more than (|A|2)(|A|2) basic operations, improves an earlier result of K. Kearnes and Á. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a k-ary near unanimity operation if and only if it contains a k-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation.

Added: Feb 5, 2021
Article
Zhuk D. Algebra Universalis. 2017. Vol. 77. No. 2. P. 191-235.

In the paper, we introduce a notion of a key relation, which is similar to the notion of a critical relation introduced by Keith A. Kearnes and Ágnes Szendrei. All clones on finite sets can be defined by only key relations. In addition, there is a nice description of all key relations on 2 elements. These are exactly the relations that can be defined as a disjunction of linear equations. In the paper, we show that in general, key relations do not have such a nice description. Nevertheless, we obtain a nice characterization of all key relations preserved by a weak near-unanimity function. This characterization is presented in the paper.

Added: Jun 15, 2020
Article
Zhuk D. Algebra Universalis. 2012. Vol. 68. No. 3-4. P. 295-320.

All minimal clones on three elements were found by B. Csákány. In this paper, for each minimal clone the cardinality of the set of all clones containing this clone is found

Added: Jun 15, 2020
Article
Zhuk D. Algebra Universalis. 2014. Vol. 71. No. 1. P. 31-54.

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.

Added: Jun 15, 2020