Simply terminating rewrite systems with long derivations

DOI10.1007/s00153-003-0190-2zbMath1113.68060OpenAlexW2045080264MaRDI QIDQ1879000

Ingo Lepper

Publication date: 22 September 2004

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-003-0190-2

zbMATH Keywords

Hardy hierarchyfundamental sequenceHydrasimple termination

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Recursive ordinals and ordinal notations (03F15) Complexity of proofs (03F20)

Related Items

An upper bound on the derivational complexity of Knuth-Bendix orderings., Beyond polynomials and Peano arithmetic -- automation of elementary and ordinal interpretations, Derivation lengths and order types of Knuth--Bendix orders, The Hydra battle and Cichon's principle