Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-10243
For citation please use:
Main Title: Local Confluence for Rules with Nested Application Conditions based on a New Critical Pair Notion
Author(s): Lambers, Leen
Ehrig, Hartmut
Habel, Annegret
Orejas, Fernando
Golas, Ulrike
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/11356
http://dx.doi.org/10.14279/depositonce-10243
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: Local confluence is an important property in many rewriting systems. The notion of critical pairs is central for being able to verify local confluence of rewriting systems in a static way. Critical pairs are defined already in the framework of graphs and adhesive rewriting systems. These systems may hold rules with or without negative application conditions. In this paper however, we consider rules with more general application conditions - also called nested application conditions - that are known to be equivalent to finite first-order graph conditions. The classical critical pair notion denotes conflicting transformations in a minimal context satisfying the application conditions. This is no longer true for combinations of positive and negative application conditions - an important special case of nested ones - where we allow that critical pairs do not satisfy the application conditions. This leads to a new notion of critical pairs which allows to formulate and prove a Local Confluence Theorem for rules with nested application conditions in the framework of adhesive rewriting systems based on the DPO-approach. It builds on a new Embedding Theorem and Completeness Theorem for critical pairs based on rules with nested application conditions. We demonstrate this new theory on the modeling of an elevator control by a typed graph transformation system with positive and negative application conditions.
Subject(s): critical pairs
local confluence
nested application conditions
graph transformation
Issue Date: 2010
Date Available: 15-Jun-2020
Has Version: 10.1007/978-3-642-15928-2_22
Language Code: en
DDC Class: 004 Datenverarbeitung; Informatik
Series: Forschungsberichte der Fakultät IV - Elektrotechnik und Informatik / Technische Universität Berlin
Series Number: 2010-07
ISSN: 1436-9915
TU Affiliation(s): Fak. 4 Elektrotechnik und Informatik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
tr_2010-07.pdf
Format: Adobe PDF | Size: 835.01 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.