C&SA | Contents

Volume 57 >>> № 5 SEPTEMBER — OCTOBER 2021

-->

UDC 004.421.6

M. Lvov¹, Y. Tarasich²

¹ Kherson State University, Kherson, Ukraine

lvov@ksu.ks.ua

² Kherson State University, Kherson, Ukraine

yutarasich@ksu.ks.ua

THE REPLENISHMENT ALGORITHM IN ALGEBRA OF SETS

Abstract. The algorithm, which, by analogy with the Buchberger and Knuth–Bendix algorithms, can be called the replenishment algorithm, is described. Specific implementations of the theoretical construction (abstract reduction system) in algebras of finite, numerical, linear semi-algebraic sets and in the algebra of multisets are described. The problem of elementary number theory, which can be interpreted as a problem of multiset algebra, is considered. The main purpose of this study is to draw attention to simple examples of application of the replenishment algorithm.

Keywords: replenishment algorithm, constructive algebras of sets, standard basis.

FULL TEXT

REFERENCES

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.

Buchberger B. et al. Computer Algebra: Symbolic and Algebraic Computing [Russian translation]. Eds. Buchberger B., Collins J., Loos R. Moscow: Mir, 1986. 392 p.

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.

Cox D., Little J., O'Shea D. Ideals, varieties and algorithms. An introduction to computational aspects of algebraic geometry and commutative algebra [Russian translation]. Moscow: Mir, 2000. 687 p.

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.