[Back]


Talks and Poster Presentations (without Proceedings-Entry):

B. Gramlich:
"Conditional Rewriting (II)";
Talk: 4th International School on Rewriting (ISR'09), Brasilia (Brazil) (invited); 2009-06-22 - 2009-06-26.



English abstract:
# Conditional Term Rewriting Systems (CTRSs) extend ordinary Term Rewriting Systems (TRSs) by allowing conditions in rewrite rules. This is a very natural and conceptually adequate extension of basic term rewriting. Although in many examples, from a purely computational point of view, conditions in rewrite rules can be avoided by an appropriate encoding within an unconditional framework, the resulting encodings are not easy to understand and to analyze. For that reason conditional term rewriting as such has been studied for a long time, with the goal of extending the basic elegant and rich theory of unconditional term rewriting to the conditional case as much as possible. Yet, it has turned out that many results, approaches, techniques and computational properties do not carry over easily, but need to be carefully adapted to make sense. In the course, starting with a thorough discussion of the basic notions and fundamental problems in conditional rewriting, a selection of the following topics will be covered (including exercises): basic format, types, classes and notions of (first-order) CTRSs
# fundamental differences/difficulties/problems as compared to TRSs
# confluence and (effective) termination properties: notions, (un)decidability, criteria, proof techniques
# CTRSs and functional-logic programming
# computatonal versus logical strength (logicality)
# modularity in conditional rewriting
# transformations from CTRSs to TRSs: soundness, completeness
# expressiveness of CTRSs as compared to TRSs

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