Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-41390
Titel: | Relating Innermost, Weak, Uniform and Modular Termination of Term Rewriting Systems |
VerfasserIn: | Gramlich, Bernhard |
Sprache: | Englisch |
Erscheinungsjahr: | 1993 |
Erscheinungsort: | Kaiserslautern |
Freie Schlagwörter: | Term rewriting systems confluence termination weak termination innermost termination modularity disjoint union combined systems with shared constructors constructor systems hierarchical combinations |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | We investigate restricted termination and confluence properties of term rewriting systems, in particular weak termination and innermost termination, and their interrelation. New criteria are provided which are sufficient for the equivalence of innermost / weak termination and uniform termination of term rewriting systems. These criteria provide interesting possibilities to infer completeness, i.e. termination plus confluence, from restricted termination and confluence properties. Using these basic results we are also able to prove some new results about modular termination of rewriting. In particular, we show that termination is modular for some classes of innermost terminating and locally confluent term rewriting systems, namely for non-overlapping and even for overlay systems. As an easy consequence this latter result also entails a simplified proof of the fact that completeness is a decomposable property of so-called constructor systems. Furthermore we show how to obtain similar results for even more general cases of (non-disjoint) combined systems with shared constructors and of certain hierarchical combinations of systems with constructors. Interestingly, these modularity results are obtained by means of a proof technique which itself constitutes a modular approach. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291--ds-413902 hdl:20.500.11880/37742 http://dx.doi.org/10.22028/D291-41390 |
Schriftenreihe: | SEKI-Report / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI [ISSN 1437-4447] |
Band: | 93,9 |
Datum des Eintrags: | 29-Mai-2024 |
Fakultät: | SE - Sonstige Einrichtungen |
Fachrichtung: | SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz |
Professur: | SE - Sonstige |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
SEKI-Report-SR-93-09_Gramlich_Relating-Innermost,-Weak,-Uniform-and-Modular-Termination-of-Term-Rewriting-Systems.pdf | 3,16 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.