УДК 004.421.6
М.С. ЛЬВОВ,
Херсонський державний університет, Івано-Франківськ, Україна,
lvov@ksu.ks.ua;;
lvovms14@gmail.com
ДИЗ’ЮНКТИВНІ БАЗИСИ ПРИКЛАДНИХ АЛГЕБР МНОЖИН ТА ЇХНЄ
ВИКОРИСТАННЯ В ЗАДАЧАХ КОМБІНАТОРНОЇ ГЕОМЕТРІЇ
Анотація. Введено поняття прикладної алгебри множин, стандартного диз’юнктивного базису прикладної а
лгебри множин і описано алгоритм побудови стандартного диз’юнктивного базису, який за аналогією з алгоритмом
Бухбергера в теорії поліноміальних ідеалів і алгоритмом Кнута–Бендикса в теорії напівгруп називається
алгоритмом критичної пари/поповнення. Наведено приклади різних прикладних алгебр множин,
до яких належать алгебра скінченних множин в реалізації на впорядкованих списках,
алгебра Лебега множин на числовій осі, алгебра лінійних напівалгебраїчних множин на площині,
алгебра кіл на площині, названа алгеброю Ейлера. Розглянуто також реалізації алгоритму критичної пари/поповнення
у цих прикладних алгебрах множин. Основний результат роботи полягає в тому,
що наявність стандартного диз’юнктивного базису дає змогу будувати ефективні за часом (поліноміальні) алгоритми розв’язання основних проблем у прикладних алгебрах множин, таких як проблема представлення, проблема належності, проблема порівняння тощо. Алгоритми в алгебрі лінійних напівалгебраїчних множин на площині та алгебрі Ейлера на площині очевидним чином можна поширити на більш загальні прикладні алгебри множин.
Ключові слова: прикладна алгебра множин, алгоритм критичної пари/поповнення, комбінаторна геометрія, проблема належності.
Присвячується світлій пам’яті академіка
Олександра Адольфовича Летичевського
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- Buchberger B. A theoretical basis for the reduction of polynomials to canonical forms. ACM SIGSAM Bulletin. 1976. Vol. 10, N 3. P. 19–29.
- Buchberger B. Basic features and development of the Critical-pair/Completion procedure. Lect. Notes Comput. Sci. 1985. Vol. 202. P. 1–45.
- Knuth D.E., Bendix P.B. Simple word problems in universal algebras. In: Computational Problems in Abstract Algebra. J. Leech (ed.). Oxford: Pergamon Press, 1970. P. 263–297.
- Cox D.A., Little J., O'Shea D. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra. 4th ed. Springer, 2015. 646 p.
- Buchberger B., Collins G.E., Loos R. Computer algebra: Symbolic and algebraic computation. Springer, 2012. 283 p.
- Winkler F. The Church–Rosser property in computer algebra and special theorem proving: An investigation of critical–pair/completion algorithms (Dissertationen der Johannes Kepler-Universitt Linz). Austria, VWGO Wien, 1984. 193 p.
- Lvov M. About one algorithm of program polynomial invariants generation. Proc. Workshop on Invariant Generation, WING 2007. 2007. P. 85–99.
- Lvov M.S. Polynomial invariants of linear cycles. Cybernetics and Systems Analysis. 2010. Vol. 46, N 4. P. 660–668.
- Lvov M. Computations in extensions of multisorted algebras. CEUR Workshop Proceedings. 2019. Vol. 2393. P. 497–512.
- Львов М.C. Об одном подходе к реализации алгебраических вычислений: вычисления в алгебре высказываний. Вестник Харк. нац. ун-та. 2009. № 863. С. 157–168.
- Lvov M., Peschanenko V., Letychevskyi O., Tarasich Y., Baiev A. Algorithm and tools for constructing canonical forms of linear semi-algebraic formulas. Cybernetics and Systems Analysis. 2018. Vol. 54, N 6. P. 993–1002. https://doi.org/10.1007/s10559-018-0102-4.
- Lvov M., Peschanenko V., Letychevskiy O., Tarasich Y. The canonical forms of logical formulae over the data types and their using in programs verification. CEUR Workshop Proceedings. 2018. Vol. 1844. P. 536–554.
- Lvov M.S. Algebraic approach to the problem of solving systems of linear inequalities. Cybernetics and Systems Analysis. 2010. Vol. 46, N 2. P. 326–339.
