Un algoritmo efectivo para la eliminación de cuantificadores

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

1995

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Descripción:

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.

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n2813_Puddu