Catálogo de publicaciones - tesis
Título de Acceso Abierto
Un algoritmo efectivo para la eliminación de cuantificadores
Susana Isabel Puddu Joos U. Heintz
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
En este trabajo se construye un algoritmo efectivo para la eliminación de cuantificadores sobre un cuerpo algebraicamente cerrado: Se demuestra que si κ es un dominio íntegro, infinito, efectivo y cerrado para la extracción de raíces p-ésimas cuando car(κ)=p>0 y φ es una fórmula prenexa con r bloques de cuantificadores que involucra a s polinomios F1,...,Fs ε κ[X1,...,Xn] entonces existe un algoritmo bien paralelizable y sin divisiones de complejidad secuencial del orden O(|φ|) + D^[(o(n))^r] que encuentra una fórmula equivalente a φ libre de cuantificaciones, donde |φ| es la longitud φ y D = máx {1+ Σ deg F1, n, s}. Este algoritmo mejora las cotas conocidas que son del orden de O(|φ|) + D^(n^cr) con c > 1 una constante universal (ver [Ie, 1989] y [Fi-Ga-Mo, 1990]). En particular se obtiene que el carácter doblemente exponencial de las cotas conocidas en el caso de un solo bloque de cuantificadores (del tipo O(|φ|) + D^(n^c) con c > 1) no es intrínseco, es decir no depende del problema sino de los algoritmos y del tipo de codificación utilizados. Los resultados obtenidos se basan fundamentalmente en el cambio del modelo de codificación de los polinomios: en vez de representar los polinomios de salida por el vector de sus coeficientes, se los codifica por medio de una red artmética sin comparaciones ni ramas que permite evaluarlos en cualquier punto. Como aplicación, se calcula la Forma de Chow de una variedad proyectiva irreducible.Palabras clave – provistas por el repositorio digital
No disponibles.
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 1995 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
1995
Información sobre licencias CC