Equations over finite linearly ordered semilattices are studied. It is assumed that the order of a semilattice is not less than the number of variables in an equation. For any equation t(X) = s(X), we find irreducible components of its solution set. We also compute the average number Irr(n) of irreducible components for all equations in n variables. It turns out that Irr(n) and the function 4/9n! are asymptotically equivalent.
Download file
Counter downloads: 184
- Title On irreducible algebraic sets over linearly ordered semilattices II
- Headline On irreducible algebraic sets over linearly ordered semilattices II
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 38
- Date:
- DOI 10.17223/20710410/38/3
Keywords
irreducible components, algebraic sets, semilattices, неприводимые компоненты, алгебраические множества, полурешеткиAuthors
References
Shevlyakov A. N. On irreducible algebraic sets over linearly ordered semilattices. Groups, Complexity, Cryptology, 2016, vol. 8, no. 2, pp. 187-196.
Daniyarova E. Yu., Myasnikov A. G., and Remeslennikov V. N. Algebraicheskaya geometriya nad algebraicheskimi sistemami [Algebraic Geometry over Algebraic Systems]. Novosibirsk, SB RAS Publ., 2016. 243 p. (in Russian)
Ben-Or M. Lower bounds for algebraic computation trees. 15th Ann. Symp. Theory Computing, 1983, pp. 80-86.
On irreducible algebraic sets over linearly ordered semilattices II | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 38. DOI: 10.17223/20710410/38/3
Download full-text version
Counter downloads: 458