Strictly orthogonal left linear rewrite systems and primitive recursion

DOI10.1016/S0168-0072(00)00041-5MaRDI QIDQ5935986zbMATH OpenFDO

Authors E. A. Cichon, E. Tahhan-Bittar

Publication date 2 July 2001

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0168-0072(00)00041-5

zbMATH Keywords

rewrite system

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Grammars and rewriting systems (68Q42)

Recommendations

• Bounding derivation lengths with functions from the slow growing hierarchy
• Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths
• Term rewriting theory for the primitive recursive functions
• scientific article; zbMATH DE number 2043536
• Termination proofs by multiset path orderings imply primitive recursive derivation lengths

Cites work

• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 599028 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 3247155 (Why is no real title available?)

Cited in

(4)

• A property of left-linear rewrite systems preserving recognizability
• scientific article; zbMATH DE number 5708984 (Why is no real title available?)
• scientific article; zbMATH DE number 2090079 (Why is no real title available?)
• Term rewriting theory for the primitive recursive functions

This page was built for publication: Strictly orthogonal left linear rewrite systems and primitive recursion

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