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
Autores principales:	Abriola, S., Figueira, S., Senno, G.
Formato:	JOUR
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:	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	todo:paper_03043975_v603_n_p3_Abriola
record_format	dspace
spelling	todo:paper_03043975_v603_n_p3_Abriola2023-10-03T15:20:29Z Linearizing well quasi-orders and bounding the length of bad sequences Abriola, S. Figueira, S. Senno, G. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Abriola, S. Figueira, S. Senno, G. 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.
format	JOUR
author	Abriola, S. Figueira, S. Senno, G.
author_facet	Abriola, S. Figueira, S. Senno, G.
author_sort	Abriola, S.
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
url	http://hdl.handle.net/20.500.12110/paper_03043975_v603_n_p3_Abriola
work_keys_str_mv	AT abriolas linearizingwellquasiordersandboundingthelengthofbadsequences AT figueiras linearizingwellquasiordersandboundingthelengthofbadsequences AT sennog linearizingwellquasiordersandboundingthelengthofbadsequences
_version_	1807316554188062720

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

Ejemplares similares