Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Giesl, Jürgen; Schneider-Kamp, Peter; Thiemann, René; Swiderski, Stephan; Nguyen, Manh Thang; De Schreye, Daniel; Serebrenik, Alexander License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-12481

; ; ; ; ; ;

Termination of Programs using Term Rewriting and SAT Solving



There are many powerful techniques for automated termination analysis of term rewrite systems (TRSs). However, up to now they have hardly been used for real programming languages. In this talk, we describe recent results which permit the application of existing techniques from term rewriting in order to prove termination of programs. We discuss two possible approaches: 1. One could translate programs into TRSs and then use existing tools to verify termination of the resulting TRSs. 2. One could adapt TRS-techniques to the respective programming languages in order to analyze programs directly. We present such approaches for the functional language Haskell and the logic language Prolog. Our results have been implemented in the termination provers AProVE and Polytool. In order to handle termination problems resulting from real programs, these provers had to be coupled with modern SAT solvers, since the automation of the TRS-termination techniques had to improve significantly. Our resulting termination analyzers are currently the most powerful ones for Haskell and Prolog.

BibTeX - Entry

  author =	{J{\"u}rgen Giesl and Peter Schneider-Kamp and Ren{\'e} Thiemann and Stephan Swiderski and Manh Thang Nguyen and Daniel De Schreye and Alexander Serebrenik},
  title =	{Termination of Programs using Term Rewriting and SAT Solving},
  booktitle =	{Deduction and Decision Procedures},
  year =	{2007},
  editor =	{Franz Baader and Byron Cook and J{\"u}rgen Giesl and Robert Nieuwenhuis},
  number =	{07401},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Termination, Term Rewriting, Haskell, Prolog, SAT Solving}

Keywords: Termination, Term Rewriting, Haskell, Prolog, SAT Solving
Seminar: 07401 - Deduction and Decision Procedures
Issue date: 2007
Date of publication: 29.11.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI