一句话：为带限制的定向条件项重写系统提出更现实的复杂度概念，并归约到无条件上下文敏感重写系统以推导复杂度界。
本文研究定向条件项重写系统（CTRS）的复杂度度量。作者指出现有复杂度概念通常只关注成功计算，忽略因规则应用失败而产生的部分计算，因而提出一种更现实的复杂度概念，适用于满足特定限制的定向 CTRS。为分析该概念，论文给出一种到无条件上下文敏感重写系统的变换，使原系统的复杂度可由目标系统反映；并发展相应技术，为变换结果推导运行时复杂度与推导复杂度上界。该工作扩展并改进了 RTA 2015 的“Conditional Complexity”，已投稿 LMCS。
We propose a notion of complexity for oriented conditional term rewrite systems satisfying certain restrictions. This notion is realistic in the sense that it measures not only successful computations, but also partial computations that result in a failed rule application. A transformation to unconditional context-sensitive rewrite systems is presented which reflects this complexity notion, as well as a technique to derive runtime and derivational complexity bounds for the result of this transformation. Comment: This is an extended and improved version of "Conditional Complexity" as published in the proceedings of RTA 2015. It has been submitted for journal publication in LMCS
@article{paperbot205,
title = {Complexity of Conditional Term Rewriting},
author = {Cynthia Kop and Aart Middeldorp and Thomas Sternagel},
journal = {Logical Methods in Computer Science},
volume = {Volume 13, Issue 1},
year = {2017},
doi = {10.23638/lmcs-13(1:6)2017}
}