Диз'юнктивні базиси прикладних алгебр множин та їхнє використання в задачах комбінаторної геометрії / Львов М. С. (2022)

English  Cybernetics and Systems Analysis   /     Issue (2022, 58 (5))

Lvov M.S.
Disjunctive bases of applied algebras of sets and their use in problems of combinatorial geometry

In this article, the concept of applied algebra of sets and a standard disjunctive basis of an applied algebra of sets are introduced. The algorithm for constructing a standard disjunctive basis is described. By analogy with Buchberger’s algorithm in the polynomial ideal theory and Knuth-Bendix’s algorithm in the theory of semigroups of words, it is called the critical pair/completion algorithm. Examples of various applied algebras of sets are provided. They include the algebra of finite sets in realization on ordered lists, the Lebesgue algebra of sets on the number axis, algebra of linear semi-algebraic sets on a plane, and algebra of circles on a plane called the Euler algebra. Implementation of the critical pair/completion algorithm is also considered. The main result of the study is that the presence of a standard disjunctive basis makes it possible to construct time-efficient (polynomial) algorithms for solving basic problems in applied algebras of sets, such as the representation problem, membership problem, equality problem, emptiness problem, etc. Algorithms in the algebra of linear semi-algebraic sets on a plane and the Euler algebra on a plane can be extended to more general applied algebras of sets. © 2022, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: algorithms of critical pair/completion, applied algebra of sets, combinatorial geometry, membership problem, representation problem, Combinatorial mathematics, Geometry, A-plane, Algorithm of critical pair/completion, Applied algebra of set, Combinatorial geometry, Completion algorithms, Membership problem, Polynomial ideal theory, Representation problem, S-algorithms, Semi-algebraic sets, Algebra

Download publication will be available after 11/01/2024 р., in 200 days

Lvov M.S. (2022). Disjunctive bases of applied algebras of sets and their use in problems of combinatorial geometry. Cybernetics and Systems Analysis, 58 (5), 149–162. doi: https://doi.org/10.1007/s10559-022-00513-7 http://jnas.nbuv.gov.ua/article/UJRN-0001348618 [In Ukrainian].


Інститут інформаційних технологій НБУВ

+38 (044) 525-36-24
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна