Hasso-Plattner-Institut
  
Hasso-Plattner-Institut
Prof. Dr. Holger Giese
  
 

20.10.2010

EATCS Best Paper Award

Am 30.09.2010 hat Leen Lambers zusammen mit ihren Koautoren Hartmut Ehrig, Annegret Habel, Fernando Orejas und Ulrike Golas für den Beitrag „Local Confluence for Rules with Nested Application Conditions“ auf der ICGT-Konferenz 2010 (International Conference on Graph Transformation) den EATCS Best Paper Award bekommen.

 

Abstract: Local confluence is an important property in many rewriting
and transformation 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 - which in the graph case are 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 have to allow that critical pairs do not satisfy all the
application conditions. This leads to a new notion of critical pairs which
allows to formulate and prove a Local Confluence Theorem for the general
case of 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.