Ordinal recursive bounds for Higman's theorem
From MaRDI portal
Publication:1129003
DOI10.1016/S0304-3975(97)00009-1zbMath0902.68100OpenAlexW2014322000MaRDI QIDQ1129003
E. A. Cichon, E. Tahhan-Bittar
Publication date: 13 August 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00009-1
Related Items (8)
Nondeterministic Ordered Restarting Automata ⋮ A characterisation of multiply recursive functions with Higman's lemma. ⋮ An upper bound on the derivational complexity of Knuth-Bendix orderings. ⋮ Higman’s Lemma and Its Computational Content ⋮ Multiply-Recursive Upper Bounds with Higman’s Lemma ⋮ Linearizing well quasi-orders and bounding the length of bad sequences ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Complexity Hierarchies beyond Elementary
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- What's so special about Kruskal's theorem and the ordinal \(\Gamma{}_ 0\)? A survey of some results in proof theory
- Ordinal complexity of recursive definitions
- Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen
- Π12-logic, Part 1: Dilators
- Accessible Independence Results for Peano Arithmetic
- A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
- Rekursionszahlen und die Grzegorczyk-Hierarchie
- A classification of the ordinal recursive functions
- Eine Klassifikation der ε0‐Rekursiven Funktionen
- Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
- An ordinal calculus for proving termination in term rewriting
This page was built for publication: Ordinal recursive bounds for Higman's theorem