Multiply-Recursive Upper Bounds with Higman’s Lemma
From MaRDI portal
Publication:3012939
DOI10.1007/978-3-642-22012-8_35zbMath1333.68179arXiv1103.4399MaRDI 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
68Q60: Specification and verification (program logics, model checking, etc.)
03D20: Recursive functions and relations, subrecursive hierarchies
03E05: Other combinatorial set theory
Related Items
Unnamed Item, The ideal view on Rackoff's coverability technique, Forward analysis and model checking for trace bounded WSTS, Ordinal recursive complexity of unordered data nets, Linearizing well quasi-orders and bounding the length of bad sequences, Handling infinitely branching well-structured transition systems, On termination and invariance for faulty channel machines, The containment problem for unambiguous register automata and unambiguous timed automata, Computable fixpoints in well-structured symbolic model checking, Generalized Post embedding problems, On the quantifier-free dynamic complexity of reachability, Complexity Hierarchies beyond Elementary, Nondeterministic Ordered Restarting Automata, On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders, The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings
Cites Work
- Unnamed Item
- Unnamed Item
- 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!
