Ordinal recursive bounds for Higman's theorem

DOI10.1016/S0304-3975(97)00009-1zbMath0902.68100MaRDI 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

zbMATH Keywords

Higman's theorem; Hardy hierarchies

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

The Parametric Complexity of Lossy Counter Machines, Linearizing well quasi-orders and bounding the length of bad sequences, A characterisation of multiply recursive functions with Higman's lemma., An upper bound on the derivational complexity of Knuth-Bendix orderings., Complexity Hierarchies beyond Elementary, Multiply-Recursive Upper Bounds with Higman’s Lemma, Nondeterministic Ordered Restarting Automata, Higman’s Lemma and Its Computational Content

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 ε₀‐Rekursiven Funktionen
• Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
• An ordinal calculus for proving termination in term rewriting