Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Capítulo o parte de un libro (BookPart)

Reducing relative termination to dependency pair problems

  • Iborra, José
  • Nishida, Naoki
  • Yamada, Akihisa
  • Vidal, Germán|||0000-0002-1857-6951
Relative termination, a generalized notion of termination, has been used in a number of different contexts like proving the confluence of rewrite systems or analyzing the termination of narrowing. In this paper, we introduce a new 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. The practical significance of our method is illustrated by means of an experimental evaluation., Germán Vidal is partially supported by the EU (FEDER) and the Spanish Ministerio de Economía y Competitividad under grant TIN2013-44742-C4-R and by the Generalitat Valenciana under grant PROMETEOII201/013. Akihisa Yamadais supported by the Austrian Science Fund (FWF): Y757
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Relative Termination via Dependency Pairs

  • Iborra, José
  • Nishida, Naoki
  • Vidal Oriola, Germán
  • Yamada, Akihisa
[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.