Ackermannian and primitive-recursive bounds with Dickson's Lemma

Dickson's Lemma is a simple yet powerful tool widely used in decidability proofs, especially when dealing with counters or related data structures in algorithmics, verification and model-checking, constraint solving, logic, etc. While Dickson's Lemma is well-known, most computer scientists...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Figueira, D., Figueira, S., Schmitz, S., Schnoebelen, P.
Formato: CONF
Materias:
Algorithmics
Computer scientists
Constraint Solving
Upper Bound
Computability and decidability
Data structures
Model checking
Computation theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_10436871_v_n_p269_Figueira
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_10436871_v_n_p269_Figueira
record_format dspace
spelling todo:paper_10436871_v_n_p269_Figueira2023-10-03T15:58:14Z Ackermannian and primitive-recursive bounds with Dickson's Lemma Figueira, D. Figueira, S. Schmitz, S. Schnoebelen, P. Algorithmics Computer scientists Constraint Solving Upper Bound Computability and decidability Data structures Model checking Computation theory Dickson's Lemma is a simple yet powerful tool widely used in decidability proofs, especially when dealing with counters or related data structures in algorithmics, verification and model-checking, constraint solving, logic, etc. While Dickson's Lemma is well-known, most computer scientists are not aware of the complexity upper bounds that are entailed by its use. This is mainly because, on this issue, the existing literature is not very accessible. We propose a new analysis of the length of bad sequences over (ℕk, ≤), improving on earlier results and providing upper bounds that are essentially tight. This analysis is complemented by a "user guide" explaining through practical examples how to easily derive complexity upper bounds from Dickson's Lemma. © 2011 IEEE. Fil:Figueira, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. CONF info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_10436871_v_n_p269_Figueira
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Algorithmics
Computer scientists
Constraint Solving
Upper Bound
Computability and decidability
Data structures
Model checking
Computation theory
spellingShingle Algorithmics
Computer scientists
Constraint Solving
Upper Bound
Computability and decidability
Data structures
Model checking
Computation theory
Figueira, D.
Figueira, S.
Schmitz, S.
Schnoebelen, P.
Ackermannian and primitive-recursive bounds with Dickson's Lemma
topic_facet Algorithmics
Computer scientists
Constraint Solving
Upper Bound
Computability and decidability
Data structures
Model checking
Computation theory
description Dickson's Lemma is a simple yet powerful tool widely used in decidability proofs, especially when dealing with counters or related data structures in algorithmics, verification and model-checking, constraint solving, logic, etc. While Dickson's Lemma is well-known, most computer scientists are not aware of the complexity upper bounds that are entailed by its use. This is mainly because, on this issue, the existing literature is not very accessible. We propose a new analysis of the length of bad sequences over (ℕk, ≤), improving on earlier results and providing upper bounds that are essentially tight. This analysis is complemented by a "user guide" explaining through practical examples how to easily derive complexity upper bounds from Dickson's Lemma. © 2011 IEEE.
format CONF
author Figueira, D.
Figueira, S.
Schmitz, S.
Schnoebelen, P.
author_facet Figueira, D.
Figueira, S.
Schmitz, S.
Schnoebelen, P.
author_sort Figueira, D.
title Ackermannian and primitive-recursive bounds with Dickson's Lemma
title_short Ackermannian and primitive-recursive bounds with Dickson's Lemma
title_full Ackermannian and primitive-recursive bounds with Dickson's Lemma
title_fullStr Ackermannian and primitive-recursive bounds with Dickson's Lemma
title_full_unstemmed Ackermannian and primitive-recursive bounds with Dickson's Lemma
title_sort ackermannian and primitive-recursive bounds with dickson's lemma
url http://hdl.handle.net/20.500.12110/paper_10436871_v_n_p269_Figueira
work_keys_str_mv AT figueirad ackermannianandprimitiverecursiveboundswithdicksonslemma
AT figueiras ackermannianandprimitiverecursiveboundswithdicksonslemma
AT schmitzs ackermannianandprimitiverecursiveboundswithdicksonslemma
AT schnoebelenp ackermannianandprimitiverecursiveboundswithdicksonslemma
_version_ 1782027820918112256

Ejemplares similares