License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07401.7
URN: urn:nbn:de:0030-drops-12481
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1248/
Go to the corresponding Portal

Giesl, Jürgen ; Schneider-Kamp, Peter ; Thiemann, René ; Swiderski, Stephan ; Nguyen, Manh Thang ; De Schreye, Daniel ; Serebrenik, Alexander

Termination of Programs using Term Rewriting and SAT Solving

pdf-format:

Abstract

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

@InProceedings{giesl_et_al:DagSemProc.07401.7,
  author =	{Giesl, J\"{u}rgen and Schneider-Kamp, Peter and Thiemann, Ren\'{e} and Swiderski, Stephan and Nguyen, Manh Thang and De Schreye, Daniel and Serebrenik, Alexander},
  title =	{{Termination of Programs using Term Rewriting and SAT Solving}},
  booktitle =	{Deduction and Decision Procedures},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7401},
  editor =	{Franz Baader and Byron Cook and J\"{u}rgen Giesl and Robert Nieuwenhuis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1248},
  URN =		{urn:nbn:de:0030-drops-12481},
  doi =		{10.4230/DagSemProc.07401.7},
  annote =	{Keywords: Termination, Term Rewriting, Haskell, Prolog, SAT Solving}
}

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

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