web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0001348618
Cybernetics and Systems Analysis   А - 2019 /  Issue (2022, Т. 58, № 5)
Львов М. С.
Диз'юнктивні базиси прикладних алгебр множин та їхнє використання в задачах комбінаторної геометрії Уведено поняття прикладної алгебри множин (ПАМ), стандартного диз'юнктивного базису прикладної алгебри множин та описано алгоритм побудови стандартного диз'юнктивного базису, який за аналогією з алгоритмом Бухбергера в теорії поліноміальних ідеалів та алгоритмом Кнута - Бендикса в теорії напівгруп називається алгоритмом критичної пари/поповнення (КПП). Наведено приклади різних ПАМ, до яких належать алгебра скінченних множин в реалізації на впорядкованих списках, алгебра Лебега множин на числовій осі, алгебра лінійних напівалгебричних множин на площині, алгебра кіл на площині, названа алгеброю Ейлера. Розглянуто також реалізації алгоритму КПП у цих ПАМ. Основний результат роботи полягає в тому, що наявність стандартного диз'юнктивного базису надає змогу будувати ефективні за часом (поліноміальні) алгоритми розв'язання основних проблем у ПАМ, таких як проблема представлення, проблема належності, проблема порівняння тощо. Алгоритми в алгебрі лінійних напівалгебричних множин на площині та алгебрі Ейлера на площині очевидним чином можна поширити на більш загальні ПАМ.
 https://doi.org/10.1007/s10559-022-00513-7
 Scopus
Бібліографічний опис:
Львов М. С. Диз'юнктивні базиси прикладних алгебр множин та їхнє використання в задачах комбінаторної геометрії. Кібернетика та системний аналіз. 2022. Т. 58, № 5. С. 149–162. doi: https://doi.org/10.1007/s10559-022-00513-7 URL: http://jnas.nbuv.gov.ua/article/UJRN-0001348618 |
 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
Cite:
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]. |
PDF