RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication
Artículo científico (JournalArticle)
Relative Termination via Dependency Pairs
[EN] A term rewrite system is terminating when no infinite reduction sequences are
possible. Relative termination generalizes termination by permitting infinite reductions as
long as some distinguished rules are not applied infinitely many times. Relative termination is
thus a fundamental notion that has been used in a number of different contexts, like analyzing
the confluence of rewrite systems or the termination of narrowing. In this work, we introduce
a novel technique to prove relative termination by reducing it to dependency pair problems.
To the best of our knowledge, this is the first significant contribution to Problem #106 of the
RTA List of Open Problems. We first present a general approach that is then instantiated to
provide a concrete technique for proving relative termination. The practical significance of
our method is illustrated by means of an experimental evaluation., Open access funding provided by Austrian Science Fund (FWF). We would like to thank Nao Hirokawa, Keiichirou Kusakari, and the anonymous reviewers for their helpful comments and suggestions in early stages of this work.