Complejidad de conjuntos semialgebraicos

Mostrar todas las versiones(3)

Sea L el lenguaje de primer orden sobre cuerpos real-cerrados. Para cada fórmula ɸ є L si P c Z [x1,...,xn] es el conjunto de polinomios que aparecen en ɸ notamos σ (ɸ): = 2 + ΣpєP deg (P) y |ɸ| := longitud de ɸ. 1. Se exhibe un algoritmo que elimina cuantificadores en L (y en partic...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Solernó, Pablo Luis
Otros Autores: Heintz, Joos
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 1989
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n2213_Solerno
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n2213_Solerno_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n2213_Solerno_oai
record_format dspace
spelling I28-R145-tesis_n2213_Solerno_oai2024-09-02 Heintz, Joos Solernó, Pablo Luis 1989 Sea L el lenguaje de primer orden sobre cuerpos real-cerrados. Para cada fórmula ɸ є L si P c Z [x1,...,xn] es el conjunto de polinomios que aparecen en ɸ notamos σ (ɸ): = 2 + ΣpєP deg (P) y |ɸ| := longitud de ɸ. 1. Se exhibe un algoritmo que elimina cuantificadores en L (y en particular descompone cilíndricamente R^n). Para cualquier fórmula ɸ en n-variables dicho algoritmo funciona en tiempos: σ(ɸ)² °(n)+o(|ɸ|) (secuencial) y 2°(n)log2^4σ(ɸ)+O(log2|ɸ|) (paralelo). Se muestra además que estas cotas superiores son optimales. 2. Dado un conjunto semialgebráico A descrito por ecuaciones e inecuaciones sobre una familia finita de polinomios F c Z [x1,...,xn], se construye un sistema de representantes para las componentes convexas de A por medio de un algoritmo que funciona en tiempos: d^n°(¹) (secuencial) y (n log2^d) °(¹) (paralelo), donde d := ΣpєP deg P. 3. Se exhibe un algoritmo tal que, dada ɸ є L, sin variables libres y escrita en forma prenexa, con r := número de bloques de cuantificadores, se decide la verdad o falsedad de ɸ en tiempos: σ(ɸ)^n°(r) (secuencial) y n°(r) (log σ(ɸ))°(¹) (paralelo). Fil: Solernó, Pablo Luis. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n2213_Solerno 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 Complejidad de conjuntos semialgebraicos 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_n2213_Solerno_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 Sea L el lenguaje de primer orden sobre cuerpos real-cerrados. Para cada fórmula ɸ є L si P c Z [x1,...,xn] es el conjunto de polinomios que aparecen en ɸ notamos σ (ɸ): = 2 + ΣpєP deg (P) y |ɸ| := longitud de ɸ. 1. Se exhibe un algoritmo que elimina cuantificadores en L (y en particular descompone cilíndricamente R^n). Para cualquier fórmula ɸ en n-variables dicho algoritmo funciona en tiempos: σ(ɸ)² °(n)+o(|ɸ|) (secuencial) y 2°(n)log2^4σ(ɸ)+O(log2|ɸ|) (paralelo). Se muestra además que estas cotas superiores son optimales. 2. Dado un conjunto semialgebráico A descrito por ecuaciones e inecuaciones sobre una familia finita de polinomios F c Z [x1,...,xn], se construye un sistema de representantes para las componentes convexas de A por medio de un algoritmo que funciona en tiempos: d^n°(¹) (secuencial) y (n log2^d) °(¹) (paralelo), donde d := ΣpєP deg P. 3. Se exhibe un algoritmo tal que, dada ɸ є L, sin variables libres y escrita en forma prenexa, con r := número de bloques de cuantificadores, se decide la verdad o falsedad de ɸ en tiempos: σ(ɸ)^n°(r) (secuencial) y n°(r) (log σ(ɸ))°(¹) (paralelo).
author2 Heintz, Joos
author_facet Heintz, Joos
Solernó, Pablo Luis
format Tesis doctoral
Tesis doctoral
publishedVersion
author Solernó, Pablo Luis
spellingShingle Solernó, Pablo Luis
Complejidad de conjuntos semialgebraicos
author_sort Solernó, Pablo Luis
title Complejidad de conjuntos semialgebraicos
title_short Complejidad de conjuntos semialgebraicos
title_full Complejidad de conjuntos semialgebraicos
title_fullStr Complejidad de conjuntos semialgebraicos
title_full_unstemmed Complejidad de conjuntos semialgebraicos
title_sort complejidad de conjuntos semialgebraicos
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 1989
url https://hdl.handle.net/20.500.12110/tesis_n2213_Solerno
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n2213_Solerno_oai
work_keys_str_mv AT solernopabloluis complejidaddeconjuntossemialgebraicos
_version_ 1824354698609557504

Ejemplares similares