УДК 004.421.6
М.С. ЛЬВОВ,
Херсонський державний університет, Херсон, Україна,
lvov@ksu.ks.ua
Ю.Г. ТАРАСІЧ,
Херсонський державний університет, Херсон, Україна,
yutarasich@ksu.ks.ua
АЛГОРИТМ ПОПОВНЕННЯ В АЛГЕБРАХ МНОЖИН
Анотація. Описано алгоритм, який за аналогією з алгоритмами Бухбергера і Кнута–Бендикса
можна назвати алгоритмом поповнення. Наведено конкретні реалізації теоретичної кон-струкції (абстрактної системи редукцій)
в алгебрах скінчених, числових, лінійних напівалгеб-раїчних множин та алгебри мультимножин. Розглянуто задачу елементарної
теорії чисел, яка може бути інтерпретована як задача алгебри мультимножин. Основна мета роботи — при-вернути увагу
до простих прикладів застосування алгоритму поповнення.
Ключові слова: алгоритм поповнення, конструктивна алгебра множин, стандартний базис.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- Buchberger B. Basic features and development of the critical-pair/completion procedure. International Conference on Rewriting Techniques and Applications. Springer, Berlin, Heidelberg. 1985. P. 1–45. https://doi.org/10.1007/3-540-15976-2_1.
- Бухбергер Б. и другие. Компьютерная алгебра: Символьные и алгебраические вычисления. Под ред. Бухбергера Б., Коллинза Дж., Лооса Р. Москва: Мир, 1986. 392 с.
- Buchberger B., Loos R. Algebraic simplification. Computer algebra. 1982. Vol. 4. P. 11–43. https://doi.org/10.1007/978-3-7091-3406-1_2.
- Knuth D., Bendix, P. Simple word problems in universal algebras. Automation of Reasoning. 1983. P. 342–376. https://doi.org/10.1007/978-3-642-81955-1_23.
- Кокс Д., Литтл Дж., О’Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. Москва: Мир, 2000. 687 с.
- Staples J. Church-roser theorems for replacement systems. Algebra and Logic. Lecture Notes in Mathematics. 1975. Vol. 450. P. 291–307. https://doi.org/10.1007/BFb0062861.
- Book R., Otto F. String-rewriting systems. String-Rewriting Systems. Text and Monographs in Computer Science. 1993. P. 35–64. https//doi.org/10.1007/978-1-4613-9771-7_3.
- Winkler F. The Church-Rosser property in computer algebra and special theorem proving: an investigation of critical-pair/completion algorithms (Ph. D. thesis). ACM SIGSAM Bulletin. 1984. Vol. 18, N 3. P. 22–22. https://doi.org/10.1145/1089389.1089396.
- Lvov M. Polynomial invariants for linear loops. Cybernetics and Systems Analysis. 2010. Vol. 46, N 4. P. 660–668. https://doi.org/10.1007/s10559-010-9242-x.
- Lvov, M., et al. 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., Letychevskyi O., Tarasich Y. The canonical forms of logical formulae over the data types and their using in programs verification. CEUR-WS. 2017. P. 536–554.
- Lvov M. Algebraic approach to the problem of solving systems of linear inequalities. Cybernetics and Systems Analysis. 2010. Vol. 46, N 2. P. 326–338. https://doi.org/ 10.1007/s10559-010-9210-5.
