Multiply-Recursive Upper Bounds with Higman’s Lemma

DOI10.1007/978-3-642-22012-8_35zbMath1333.68179arXiv1103.4399OpenAlexW2138781755MaRDI QIDQ3012939

No author found.

Publication date: 7 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1103.4399

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Recursive functions and relations, subrecursive hierarchies (03D20) Other combinatorial set theory (03E05)

Related Items (17)

Forward analysis and model checking for trace bounded WSTS ⋮ Nondeterministic Ordered Restarting Automata ⋮ Handling infinitely branching well-structured transition systems ⋮ On termination and invariance for faulty channel machines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders ⋮ The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings ⋮ Computable fixpoints in well-structured symbolic model checking ⋮ Ordinal recursive complexity of unordered data nets ⋮ The ideal view on Rackoff's coverability technique ⋮ On the quantifier-free dynamic complexity of reachability ⋮ The containment problem for unambiguous register automata and unambiguous timed automata ⋮ Linearizing well quasi-orders and bounding the length of bad sequences ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Complexity Hierarchies beyond Elementary ⋮ Generalized Post embedding problems

Cites Work

• Petri nets and large finite sets
• Ordinal recursive bounds for Higman's theorem
• A characterisation of multiply recursive functions with Higman's lemma.
• On the finite containment problem for Petri nets
• Algorithmic analysis of programs with well quasi-ordered domains.
• Complexity bounds for some finite forms of Kruskal's theorem
• The theory of well-quasi-ordering: a frequently discovered concept
• Lossy Counter Machines Decidability Cheat Sheet
• Pumping and Counting on the Regular Post Embedding Problem
• A Uniform Approach to Fundamental Sequences and Hierarchies
• A classification of symbolic transition systems
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
• Hierarchies of number-theoretic functions. I
• Well-structured transition systems everywhere!
• Unnamed Item
• Unnamed Item

This page was built for publication: Multiply-Recursive Upper Bounds with Higman’s Lemma