2011/03/25 by Georg Moser, Moser, Georg, Andreas Schnabl +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1103.5082
22 pages, extended conference version
arxiv created 2011/03/25 · openalex publication_date 2011/03/25 · arxiv updated 2011/03/29 · openalex created_date 2025/10/27 · openalex updated_date 2026/07/28
We study the derivational complexity of rewrite systems whose termination is provable in the dependency pair framework using the processors for reduction pairs, dependency graphs, or the subterm criterion. We show that the derivational complexity of such systems is bounded by a multiple recursive function, provided the derivational complexity induced by the employed base techniques is at most multiple recursive. Moreover we show that this upper bound is tight.