Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders

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 develop a new, self-contained...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Abriola, S., Figueira, S., Senno, G.
Formato: SER
Materias:
Data tree
Decision procedure
Mathematical tools
Multi-sets
Product ordering
Upper Bound
Algorithms
Trees (mathematics)
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v7456LNCS_n_p110_Abriola
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03029743_v7456LNCS_n_p110_Abriola
record_format dspace
spelling todo:paper_03029743_v7456LNCS_n_p110_Abriola2023-10-03T15:19:29Z Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders Abriola, S. Figueira, S. Senno, G. Data tree Decision procedure Mathematical tools Multi-sets Product ordering Upper Bound Algorithms Trees (mathematics) 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 develop a new, self-contained study of the length of bad sequences over the product ordering of ℕ n , which leads to known results but with a much simpler argument. We also give a new tight upper bound for the length of the longest controlled descending sequence of multisets of ℕ n, and use it to give an upper bound for the length of controlled bad sequences in the majoring ordering of sets of tuples. We apply this upper bound to obtain complexity upper bounds for decision procedures of automata over data trees. In both cases the idea is to linearize bad sequences, i.e. transform them into a descending one over a well-order for which upper bounds can be more easily handled. © 2012 Springer-Verlag. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v7456LNCS_n_p110_Abriola
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Data tree
Decision procedure
Mathematical tools
Multi-sets
Product ordering
Upper Bound
Algorithms
Trees (mathematics)
spellingShingle Data tree
Decision procedure
Mathematical tools
Multi-sets
Product ordering
Upper Bound
Algorithms
Trees (mathematics)
Abriola, S.
Figueira, S.
Senno, G.
Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders
topic_facet Data tree
Decision procedure
Mathematical tools
Multi-sets
Product ordering
Upper Bound
Algorithms
Trees (mathematics)
description 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 develop a new, self-contained study of the length of bad sequences over the product ordering of ℕ n , which leads to known results but with a much simpler argument. We also give a new tight upper bound for the length of the longest controlled descending sequence of multisets of ℕ n, and use it to give an upper bound for the length of controlled bad sequences in the majoring ordering of sets of tuples. We apply this upper bound to obtain complexity upper bounds for decision procedures of automata over data trees. In both cases the idea is to linearize bad sequences, i.e. transform them into a descending one over a well-order for which upper bounds can be more easily handled. © 2012 Springer-Verlag.
format SER
author Abriola, S.
Figueira, S.
Senno, G.
author_facet Abriola, S.
Figueira, S.
Senno, G.
author_sort Abriola, S.
title Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders
title_short Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders
title_full Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders
title_fullStr Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders
title_full_unstemmed Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders
title_sort linearizing bad sequences: upper bounds for the product and majoring well quasi-orders
url http://hdl.handle.net/20.500.12110/paper_03029743_v7456LNCS_n_p110_Abriola
work_keys_str_mv AT abriolas linearizingbadsequencesupperboundsfortheproductandmajoringwellquasiorders
AT figueiras linearizingbadsequencesupperboundsfortheproductandmajoringwellquasiorders
AT sennog linearizingbadsequencesupperboundsfortheproductandmajoringwellquasiorders
_version_ 1807322166205612032

Ejemplares similares