Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | matematica |
| Título: | Un algoritmo efectivo para la eliminación de cuantificadores |
| Autor: | Puddu, Susana Isabel |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Filiación: | Departamento de Matemática
|
| Publicación en la Web: | 2013-11-22 |
| Fecha de defensa: | 1995 |
| Fecha en portada: | 1995 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor en Ciencias Matemáticas |
| Director: | Heintz, Joos U. |
| Idioma: | Español |
| Tema: | matemática/álgebra
|
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n2813_Puddu |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n2813_Puddu.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n2813_Puddu |
| Ubicación: | Dep.002813 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Puddu, Susana Isabel. (1995). Un algoritmo efectivo para la eliminación de cuantificadores. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n2813_Puddu |
Resumen:
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.
Citación:
---------- APA ----------
Puddu, Susana Isabel. (1995). Un algoritmo efectivo para la eliminación de cuantificadores. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n2813_Puddu
---------- CHICAGO ----------
Puddu, Susana Isabel. "Un algoritmo efectivo para la eliminación de cuantificadores". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 1995.https://hdl.handle.net/20.500.12110/tesis_n2813_Puddu
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n2813_Puddu.pdf
