Publications in Scientific Journals:

B. Gramlich, F. Schernhammer:
"Termination of Rewriting with and Automated Synthesis of Forbidden Patterns";
Electronic Proceedings in Theoretical Computer Science, 44 (2010), 35 - 50.

English abstract:
We introduce a modified version of the well-known dependency pair framework that is suitable for the termination analysis of rewriting under forbidden pattern restrictions. By attaching contexts to dependency pairs that represent the calling contexts of the corresponding recursive function calls, it is possible to incorporate the forbidden pattern restrictions in the (adapted) notion of dependency pair chains, thus yielding a sound and complete approach to termination analysis. Building upon this contextual depetextual dependency pair framework we introduce a DP processor that simplifies problems by analyzing the contextual information of the dependency pairs. Moreover, we show how this processor can be used to synthesize forbidden patterns suitable for a given TRS on-the-fly during the termination analysis.

rewriting with forbidden patterns, contextual textual dependency pair framework, proving termination

Electronic version of the publication:

Created from the Publication Database of the Vienna University of Technology.