UDC 004.421.6
DISJUNCTIVE BASES OF APPLIED ALGEBRAS OF SETS AND THEIR USE IN PROBLEMS
OF COMBINATORIAL GEOMETRY
Abstract. In this paper, the concepts 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 polynomial ideal theory and Knuth–Bendix’s algorithm in the theory of semi groups 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.
Implementations of the critical pair/completion algorithm are 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.
Keywords: applied algebra of sets, algorithm of critical pair/completion, combinatorial geometry, membership problem, representation problem.
FULL TEXT
REFERENCES
- 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.
