Un algoritmo efectivo para la eliminación de cuantificadores

Mostrar todas las versiones(3)

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 blo...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Puddu, Susana Isabel
Otros Autores: Heintz, Joos U.
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 1995
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n2813_Puddu
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n2813_Puddu_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n2813_Puddu_oai
record_format dspace
spelling I28-R145-tesis_n2813_Puddu_oai2024-09-02 Heintz, Joos U. Puddu, Susana Isabel 1995 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. Fil: Puddu, Susana Isabel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n2813_Puddu spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar Un algoritmo efectivo para la eliminación de cuantificadores info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n2813_Puddu_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Español
orig_language_str_mv spa
description 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.
author2 Heintz, Joos U.
author_facet Heintz, Joos U.
Puddu, Susana Isabel
format Tesis doctoral
Tesis doctoral
publishedVersion
author Puddu, Susana Isabel
spellingShingle Puddu, Susana Isabel
Un algoritmo efectivo para la eliminación de cuantificadores
author_sort Puddu, Susana Isabel
title Un algoritmo efectivo para la eliminación de cuantificadores
title_short Un algoritmo efectivo para la eliminación de cuantificadores
title_full Un algoritmo efectivo para la eliminación de cuantificadores
title_fullStr Un algoritmo efectivo para la eliminación de cuantificadores
title_full_unstemmed Un algoritmo efectivo para la eliminación de cuantificadores
title_sort un algoritmo efectivo para la eliminación de cuantificadores
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 1995
url https://hdl.handle.net/20.500.12110/tesis_n2813_Puddu
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n2813_Puddu_oai
work_keys_str_mv AT puddususanaisabel unalgoritmoefectivoparalaeliminaciondecuantificadores
_version_ 1824355425805402112

Ejemplares similares