Linearizing well quasi-orders and bounding the length of bad sequences

We study the length functions of controlled bad sequences over some well quasi-orders (wqo's) and classify them in the Fast Growing Hierarchy. We develop a new and self-contained study of the length of bad sequences over the disjoint product in Nn (Dickson's Lemma), which leads to recently...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Figueira, Santiago Daniel
Publicado:	2015
Materias:	Controlled bad sequence Fast Growing Hierarchy Lexicographic ordering Majoring ordering Multiset ordering Product ordering Well quasi-order Lexicographic order Well quasi orderings Computational methods
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v603_n_p3_Abriola http://hdl.handle.net/20.500.12110/paper_03043975_v603_n_p3_Abriola
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03043975_v603_n_p3_Abriola
record_format	dspace
spelling	paper:paper_03043975_v603_n_p3_Abriola2023-06-08T15:29:40Z Linearizing well quasi-orders and bounding the length of bad sequences Figueira, Santiago Daniel Controlled bad sequence Fast Growing Hierarchy Lexicographic ordering Majoring ordering Multiset ordering Product ordering Well quasi-order Controlled bad sequence Fast Growing Hierarchy Lexicographic order Majoring ordering Multiset ordering Product ordering Well quasi orderings Computational methods We study the length functions of controlled bad sequences over some well quasi-orders (wqo's) and classify them in the Fast Growing Hierarchy. We develop a new and self-contained study of the length of bad sequences over the disjoint product in Nn (Dickson's Lemma), which leads to recently discovered upper bounds but through a simpler argument. We also give a tight upper bound for the length of controlled decreasing sequences of multisets of Nn with the underlying lexicographic ordering, and use it to give an upper bound for the length of controlled bad sequences in the majoring ordering with the underlying disjoint product ordering. We apply this last result to attain complexity upper bounds for the emptiness problem of itca and atra automata. For the case of the product and majoring wqo's the idea is to linearize bad sequences, i.e. to transform a bad sequence over a wqo into a decreasing one over a well-order, for which upper bounds can be more easily handled. © 2015 Elsevier B.V. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v603_n_p3_Abriola http://hdl.handle.net/20.500.12110/paper_03043975_v603_n_p3_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	Controlled bad sequence Fast Growing Hierarchy Lexicographic ordering Majoring ordering Multiset ordering Product ordering Well quasi-order Controlled bad sequence Fast Growing Hierarchy Lexicographic order Majoring ordering Multiset ordering Product ordering Well quasi orderings Computational methods
spellingShingle	Controlled bad sequence Fast Growing Hierarchy Lexicographic ordering Majoring ordering Multiset ordering Product ordering Well quasi-order Controlled bad sequence Fast Growing Hierarchy Lexicographic order Majoring ordering Multiset ordering Product ordering Well quasi orderings Computational methods Figueira, Santiago Daniel Linearizing well quasi-orders and bounding the length of bad sequences
topic_facet	Controlled bad sequence Fast Growing Hierarchy Lexicographic ordering Majoring ordering Multiset ordering Product ordering Well quasi-order Controlled bad sequence Fast Growing Hierarchy Lexicographic order Majoring ordering Multiset ordering Product ordering Well quasi orderings Computational methods
description	We study the length functions of controlled bad sequences over some well quasi-orders (wqo's) and classify them in the Fast Growing Hierarchy. We develop a new and self-contained study of the length of bad sequences over the disjoint product in Nn (Dickson's Lemma), which leads to recently discovered upper bounds but through a simpler argument. We also give a tight upper bound for the length of controlled decreasing sequences of multisets of Nn with the underlying lexicographic ordering, and use it to give an upper bound for the length of controlled bad sequences in the majoring ordering with the underlying disjoint product ordering. We apply this last result to attain complexity upper bounds for the emptiness problem of itca and atra automata. For the case of the product and majoring wqo's the idea is to linearize bad sequences, i.e. to transform a bad sequence over a wqo into a decreasing one over a well-order, for which upper bounds can be more easily handled. © 2015 Elsevier B.V.
author	Figueira, Santiago Daniel
author_facet	Figueira, Santiago Daniel
author_sort	Figueira, Santiago Daniel
title	Linearizing well quasi-orders and bounding the length of bad sequences
title_short	Linearizing well quasi-orders and bounding the length of bad sequences
title_full	Linearizing well quasi-orders and bounding the length of bad sequences
title_fullStr	Linearizing well quasi-orders and bounding the length of bad sequences
title_full_unstemmed	Linearizing well quasi-orders and bounding the length of bad sequences
title_sort	linearizing well quasi-orders and bounding the length of bad sequences
publishDate	2015
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v603_n_p3_Abriola http://hdl.handle.net/20.500.12110/paper_03043975_v603_n_p3_Abriola
work_keys_str_mv	AT figueirasantiagodaniel linearizingwellquasiordersandboundingthelengthofbadsequences
_version_	1768544224532234240

Linearizing well quasi-orders and bounding the length of bad sequences

Ejemplares similares