Resumen:
Una secuencia x₀, x₁, x₂, ... sobre un conjunto C provisto de un cuasi-orden ≤ es mala cuando i < j implica xᵢ ≰ xⱼ. A priori, la longitud de tales secuencias no está acotada. Las secuencias controladas son aquellas en donde se puede medir de alguna manera efectiva cuánto puede crecer el tamaño de cada xᵢ. Los cuasi-órdenes bien fundados y este tipo de secuencias malas controladas son muy usados en pruebas de decidibilidad en autómatas con contadores o estructuras de datos relacionadas en algoritmia, verificación, model-checking, lógica, etc. En esta tesis estudiamos cotas superiores e inferiores para la longitud máxima de secuencias malas controladas sobre algunos cuasi-órdenes, y clasificamos estas cotas en la Jerarquía Rápidamente Creciente. Puntualmente, damos una demostración constructiva y sencilla del Lema de Dickson, que a su vez nos permite acotar la longitud máxima de las secuencias malas de tuplas de naturales y el orden producto. Estudiamos la longitud de las secuencias malas controladas de conjuntos de tuplas de naturales con el orden mayorante, y también investigamos el caso de los multiconjuntos. La técnica general que usamos consiste en reducir el problema de la longitud de secuencias malas controladas sobre un cuasi-orden al de la longitud de las secuencias decrecientes y controladas más largas sobre un buen orden.
Citación:
---------- APA ----------
Abriola, Sergio Alejandro. (2011). Sobre la longitud de las secuencias malas controladas en cuasi-órdenes buenos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000773_Abriola
---------- CHICAGO ----------
Abriola, Sergio Alejandro. "Sobre la longitud de las secuencias malas controladas en cuasi-órdenes buenos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2011.https://hdl.handle.net/20.500.12110/seminario_nMAT000773_Abriola
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000773_Abriola.pdf
Distrubución geográfica
