2.4k citations
- Austrian Academy of SciencesAT135 papers
- Institute for Quantum Optics and Quantum Information InnsbruckAT123 papers
- Centre National de la Recherche ScientifiqueFR73 papers
- Université Paris CitéFR58 papers
- Commissariat à l'Énergie Atomique et aux Énergies AlternativesFR57 papers
- CEA Paris-SaclayFR55 papers
- Stockholm UniversitySE55 papers
- Institut de Recherche sur les Lois Fondamentales de l'UniversFR53 papers
- Institut National de Physique Nucléaire et de Physique des ParticulesFR52 papers
- Istituto Nazionale di Fisica Nucleare, Sezione di PisaIT48 papers
- Heidelberg UniversityDE47 papers
- The Ohio State UniversityUS47 papers
9 papers · 1 filter
Confluence by Decreasing Diagrams -- Formalized
Harald Zankl
This paper presents a formalization of decreasing diagrams in the theorem prover Isabelle. It discusses mechanical proofs showing that any locally decreasing abstract rewrite syste…
A Relative Dependency Pair Framework
Christian Sternagel, René Thiemann
In this paper we generalize the DP framework to a relative DP framework, where a so called split is possible.
Termination Proofs in the Dependency Pair Framework May Induce Multiple Recursive Derivational Complexity
Georg Moser, Andreas Schnabl
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,…
Uncurrying for Innermost Termination and Derivational Complexity
Harald Zankl, Nao Hirokawa, Aart Middeldorp
First-order applicative term rewriting systems provide a natural framework for modeling higher-order aspects. In earlier work we introduced an uncurrying transformation which is te…
Automated Complexity Analysis Based on the Dependency Pair Method
Nao Hirokawa, Georg Moser
This article is concerned with automated complexity analysis of term rewrite systems. Since these systems underlie much of declarative programming, time complexity of functions def…
Loops under Strategies ... Continued
René Thiemann, Christian Sternagel, Jürgen Giesl +1
While there are many approaches for automatically proving termination of term rewrite systems, up to now there exist only few techniques to disprove their termination automatically…