Registro:
| Documento: | Tesis de Grado |
| Título: | Cota superior para la longitud de secuencias malas en el orden mayorante con aplicación a complejidad de problemas de decisión en autómatas sobre árboles |
| Título alternativo: | Upper bound for the length of bad sequences in the majoring ordering with an application to complexity of decision problems in tree automata |
| Autor: | Senno, Gabriel Ignacio |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2012 |
| Fecha en portada: | 14 Agosto 2012 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Figueira, Santiago Daniel |
| Jurado: | Jacobo Berlles, Julio César Alberto; Zabala, Paula Lorena |
| Idioma: | Inglés |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000735_Senno |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000735_Senno.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000735_Senno |
| Ubicación: | Dep.COM 000735 |
| 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. Senno, Gabriel Ignacio. (2012). Cota superior para la longitud de secuencias malas en el orden mayorante con aplicación a complejidad de problemas de decisión en autómatas sobre árboles. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000735_Senno |
Abstract:
Well quasi-orders (wqo’s) are an important mathematical tool for proving termination of many algorithms. Under some assumptions upper bounds for the computational complexity of such algorithms can be extracted by analyzing the length of controlled bad sequences. We obtain tight upper bounds, in terms of the Fast Growing Hierarchy, for the length of controlled decreasing sequences of multisets over the natural multiset ordering. Then we study the majoring wqo ≤maj of sets of tuples, which informally states that A ≤maj B iff every element of A is majorized by an element of B. We linearize this wqo into the multiset wellorder, to obtain an upper bound for the length of controlled ≤maj-bad sequences. We finally apply this result to upper-bound the computational complexity of the emptiness problem for ATRA, a class of automata over data trees.
Citación:
---------- APA ----------
Senno, Gabriel Ignacio. (2012). Cota superior para la longitud de secuencias malas en el orden mayorante con aplicación a complejidad de problemas de decisión en autómatas sobre árboles. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000735_Senno
---------- CHICAGO ----------
Senno, Gabriel Ignacio. "Cota superior para la longitud de secuencias malas en el orden mayorante con aplicación a complejidad de problemas de decisión en autómatas sobre árboles". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2012.https://hdl.handle.net/20.500.12110/seminario_nCOM000735_Senno
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000735_Senno.pdf
Distrubución geográfica
