- 1.BEN-OR, M., KOZEN, D., AND REw, j. The complexity of elementary algebra and geometry. J. Comput. Syst. Sci. 3~ (1985), 251-264. Google ScholarDigital Library
- 2.BUCHBERGER, B., COLLINS, G. E., AND KUTZLER, B. Algebraic methods for geometric reasoning. Ann. Rev. Comput. Sci. 3 (1988), 85-119. Google ScholarDigital Library
- 3.CHISTOV, A. L. An algorithm of polynomial complexity for factoring polynomials, and determination of the components of n variety in a subexponential time. Zap. Nauchn. Se,. Leningrad. Otdel. Inst. Steklov (LOMI) 137 (1984), 124-188. Russian, English summary.Google Scholar
- 4.DICRESCENZO, C., AND DUVAL, D. Computations on curves, vol. 174 of Lex.~ure Notes in Computer Science. Springer, 1984, pp. 100-107. Google ScholarDigital Library
- 5.DICRESCENZO, C., AND DUVAL, D. Algebraic computations on algebraic numbers. In In.formatique et Calcul. Wiley-Masson, 1985, pp. 54-61.Google Scholar
- 6.GALLO, G., AND MISHRA, B. Wu-Ritt characteristic sets and their complexity. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 6 (1991), 111-136.Google ScholarCross Ref
- 7.GIUSTI, M., AND HEINTZ, J. Algorithmes- disons rnpides - pour la decomposition d'une vari(~t6 aig6brique en composantes irrdductibles et &tuidimensionnelles. In Effective Methods in Algebraic Geometry, T. Morn and C. Trnverso, Eds. Birkh~iuser, 1991, pp. 169-194.Google ScholarCross Ref
- 8.GRIGOR~:V, D. Y. Factoring polynomials over a finite field and solving systems of algebraic equations. Zap. Nauchn. Se,. Leningrad. Otdel. Inst. Steklov (LOMI) 137 (1984), 20-79. Russian, English summary.Google Scholar
- 9.HARTSHORNE, R. Algebraic Geometry. Springer- Verlng, 1977.Google Scholar
- 10.IERARDI, D., AND KOZEN, D. Parallel resultant computation. In Synthesis of Parallel Algorithms, J. Reif, Ed. Morgan Kauffman, 1993, pp. 679--720.Google Scholar
- 11.IERARDI, D. J. The eomplezity of quantifier elimination in the theory of an algebraically closed field. PhD thesis, Cornell University, 1989. Google ScholarDigital Library
- 12.KALKBRENER, M. Algorithmic properties of polynomial rings. Habilitationsschrift.Google Scholar
- 13.KALKBRENER, M. Prime decomposition of radicals in polynomial rings. J. Symbolic Computation 18 (1994), 365-372. Google ScholarDigital Library
- 14.KOZEN, D. E~cient resolution of singularities of plane curves. Tech. rep., Cornell University, Mathematical Science Institute, 1994. Google ScholarDigital Library
- 15.LAZARD, D. Resolution des systemes d'equntions algebriques. Theoret. Comp. Sci. i5, 1 (1981). French, English summary.Google Scholar
- 16.RITT, J. F. Differential algebra. American Mathematical Society, 1950.Google ScholarCross Ref
- 17.STURMFELS, B. Sparse elimination theory. In Computational algebraic geometry and commutative algebra, D. Eisenbud and L. Robbiano, Eds. Cambridge, 1991, pp. 264-298.Google Scholar
- 18.TEITELBAUM, J. The computational complexity of the resolution of plane curve singularities. Math. Comp. 54 (1990), 797-837.Google ScholarCross Ref
- 19.YON ZUR GATHEN, J. Parallel algorithms for algebraic problems. SIAM J. Comput. 13, 4 (1984), 802-824. Google ScholarDigital Library
- 20.WANG, D. Irreducible decomposition of algebraic varieties via characteristic sets and GrSbner bases. Computer Aided Geometric Design 9 (1992), 471-484. Google ScholarDigital Library
- 21.WANG) D. Elimination method for mechanical theorem proving in geometries. Annals of Math. and Artificial Intelligence I3 (1995), 1-24.Google Scholar
- 22.Wo, W.-T. Basic principles of mechanical theorem proving in elementary geometries. J. Syst. Sci. Math. Sci. 4 (1984), 207-235.Google Scholar
Index Terms
- Complexity of the Wu-Ritt decomposition
Recommendations
On Ritt's decomposition theorem in the case of finite fields
A classical theorem by Ritt states that all the complete decomposition chains of a univariate polynomial satisfying a certain tameness condition have the same length. In this paper we present our conclusions about the generalization of these theorem in ...
Normal form for Ritt's Second Theorem
Ritt's Second Theorem deals with composition collisionsg@?h=g^@?@?h^@? of univariate polynomials over a field, where degg=degh^@?. Joseph Fels Ritt (1922) presented two types of such decompositions. His main result here is that these comprise all ...
Comments