Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We show that the known algorithms used to re-write any first order quantifier-free formula over an algebraically closed field into its normal disjunctive form are essentially optimal. This result follows from an estimate of the number of sets definable by equalities and inequalities of fixed polynomials. Finally we apply our results to obtain similar estimates in the real case. © 2000 Academic Press.

Registro:

Documento: Artículo
Título:On the number of sets definable by polynomials
Autor:Jeronimo, G.; Sabia, J.
Filiación:Departamento de Matemática, Facultad de Ciencias y Exactas Nat., Universidad de Buenos Aires, Pab. I, 1428 Buenos Aires, Argentina
Palabras clave:Algebraic complexity; Algorithms; Polynomial-definable sets
Año:2000
Volumen:227
Número:2
Página de inicio:633
Página de fin:644
DOI: http://dx.doi.org/10.1006/jabr.1999.8243
Título revista:Journal of Algebra
Título revista abreviado:J. Algebra
ISSN:00218693
CODEN:JALGA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00218693_v227_n2_p633_Jeronimo

Referencias:

  • Fitchas, N., Galligo, A., Morgenstern, J., Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields (1990) J. Pure Appl. Algebra, 67, pp. 1-14
  • Grigor'ev D. Yu, Complexity of deciding Tarski algebra (1988) J. Symbolic Comput., 5, pp. 65-108
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24, pp. 239-277
  • Pollack, R., Roy, M.-F., On the number of cells defined by a set of polynomials (1993) C. R. Acad. Sci. Paris, 316, pp. 573-577
  • Warren H., E., Lower bounds for approximation of nonlinear manifolds (1968) Trans. Amer. Math. Soc., 133, pp. 167-178

Citas:

---------- APA ----------
Jeronimo, G. & Sabia, J. (2000) . On the number of sets definable by polynomials. Journal of Algebra, 227(2), 633-644.
http://dx.doi.org/10.1006/jabr.1999.8243
---------- CHICAGO ----------
Jeronimo, G., Sabia, J. "On the number of sets definable by polynomials" . Journal of Algebra 227, no. 2 (2000) : 633-644.
http://dx.doi.org/10.1006/jabr.1999.8243
---------- MLA ----------
Jeronimo, G., Sabia, J. "On the number of sets definable by polynomials" . Journal of Algebra, vol. 227, no. 2, 2000, pp. 633-644.
http://dx.doi.org/10.1006/jabr.1999.8243
---------- VANCOUVER ----------
Jeronimo, G., Sabia, J. On the number of sets definable by polynomials. J. Algebra. 2000;227(2):633-644.
http://dx.doi.org/10.1006/jabr.1999.8243