Ordinal recursive bounds for Higman's theorem

DOI10.1016/S0304-3975(97)00009-1MaRDI QIDQ1129003zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

Higman's theoremHardy hierarchies

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Multiply-recursive upper bounds with Higman's lemma
• A characterisation of multiply recursive functions with Higman's lemma.
• Publication:4938604
• scientific article; zbMATH DE number 2085177
• Complexity bounds for some finite forms of Kruskal's theorem

Cites work

• scientific article; zbMATH DE number 3920456 (Why is no real title available?)
• scientific article; zbMATH DE number 3677903 (Why is no real title available?)
• scientific article; zbMATH DE number 3247155 (Why is no real title available?)
• scientific article; zbMATH DE number 3252233 (Why is no real title available?)
• scientific article; zbMATH DE number 3355016 (Why is no real title available?)
• A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
• A classification of the ordinal recursive functions
• Accessible Independence Results for Peano Arithmetic
• An ordinal calculus for proving termination in term rewriting
• Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen
• Eine Klassifikation der ε₀‐Rekursiven Funktionen
• Ordinal complexity of recursive definitions
• Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
• Rekursionszahlen und die Grzegorczyk-Hierarchie
• What's so special about Kruskal's theorem and the ordinal \(\Gamma{}_ 0\)? A survey of some results in proof theory
• Π12-logic, Part 1: Dilators

Cited in

(10)

• Higman's lemma and its computational content
• Nondeterministic ordered restarting automata
• A characterisation of multiply recursive functions with Higman's lemma.
• The Parametric Complexity of Lossy Counter Machines
• An upper bound on the derivational complexity of Knuth-Bendix orderings.
• Linearizing well quasi-orders and bounding the length of bad sequences
• Multiply-recursive upper bounds with Higman's lemma
• Complexity of controlled bad sequences over finite sets of \(\mathbb{N}^d\)
• scientific article; zbMATH DE number 1405625 (Why is no real title available?)
• Complexity hierarchies beyond elementary

This page was built for publication: Ordinal recursive bounds for Higman's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1129003)