pith. machine review for the scientific record. sign in

arxiv: 1103.4399 · v2 · submitted 2011-03-22 · 💻 cs.LO · cs.CC

Recognition: unknown

Multiply-Recursive Upper Bounds with Higman's Lemma

Sylvain Schmitz , Philippe Schnoebelen
Authors on Pith no claims yet
classification 💻 cs.LO cs.CC
keywords boundshigmanlemmamultiply-recursiveupperalgorithmsanalysisapply
0
0 comments X
read the original abstract

We develop a new analysis for the length of controlled bad sequences in well-quasi-orderings based on Higman's Lemma. This leads to tight multiply-recursive upper bounds that readily apply to several verification algorithms for well-structured systems.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The Complexity of Nested Reset Counter Systems

    cs.FL 2026-05 unverdicted novelty 8.0

    Coverability for order-k nested reset counter systems is F_Ωk-complete.