@article{LambersOrejas2021,
  author    = {Lambers, Leen and Orejas, Fernando},
  title     = {Transformation rules with nested application conditions},
  series = {Theoretical computer science},
  volume    = {884},
  journal   = {Theoretical computer science},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {0304-3975},
  doi       = {10.1016/j.tcs.2021.07.023},
  pages     = {44 -- 67},
  year      = {2021},
  abstract  = {Recently, initial conflicts were introduced in the framework of M-adhesive categories as an important optimization of critical pairs. In particular, they represent a proper subset such that each conflict is represented in a minimal context by a unique initial one. The theory of critical pairs has been extended in the framework of M-adhesive categories to rules with nested application conditions (ACs), restricting the applicability of a rule and generalizing the well-known negative application conditions. A notion of initial conflicts for rules with ACs does not exist yet. In this paper, on the one hand, we extend the theory of initial conflicts in the framework of M-adhesive categories to transformation rules with ACs. They represent a proper subset again of critical pairs for rules with ACs, and represent each conflict in a minimal context uniquely. They are moreover symbolic because we can show that in general no finite and complete set of conflicts for rules with ACs exists. On the other hand, we show that critical pairs are minimally M-complete, whereas initial conflicts are minimally complete. Finally, we introduce important special cases of rules with ACs for which we can obtain finite, minimally (M-)complete sets of conflicts.},
  language  = {en}
}
@book{GieseHildebrandtLambers2010,
  author    = {Giese, Holger and Hildebrandt, Stephan and Lambers, Leen},
  title     = {Toward bridging the gap between formal semantics and implementation of triple graph grammars},
  publisher = {Universit{\"a}tsverlag Potsdam},
  address   = {Potsdam},
  isbn      = {978-3-86956-078-6},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-45219},
  publisher      = {Universit{\"a}t Potsdam},
  pages     = {26},
  year      = {2010},
  abstract  = {The correctness of model transformations is a crucial element for the model-driven engineering of high quality software. A prerequisite to verify model transformations at the level of the model transformation specification is that an unambiguous formal semantics exists and that the employed implementation of the model transformation language adheres to this semantics. However, for existing relational model transformation approaches it is usually not really clear under which constraints particular implementations are really conform to the formal semantics. In this paper, we will bridge this gap for the formal semantics of triple graph grammars (TGG) and an existing efficient implementation. Whereas the formal semantics assumes backtracking and ignores non-determinism, practical implementations do not support backtracking, require rule sets that ensure determinism, and include further optimizations. Therefore, we capture how the considered TGG implementation realizes the transformation by means of operational rules, define required criteria and show conformance to the formal semantics if these criteria are fulfilled. We further outline how static analysis can be employed to guarantee these criteria.},
  language  = {en}
}
@book{SchneiderLambersOrejas2017,
  author    = {Schneider, Sven and Lambers, Leen and Orejas, Fernando},
  title     = {Symbolic model generation for graph properties},
  number    = {115},
  publisher = {Universit{\"a}tsverlag Potsdam},
  address   = {Potsdam},
  isbn      = {978-3-86956-396-1},
  issn      = {1613-5652},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-103171},
  publisher      = {Universit{\"a}t Potsdam},
  pages     = {48},
  year      = {2017},
  abstract  = {Graphs are ubiquitous in Computer Science. For this reason, in many areas, it is very important to have the means to express and reason about graph properties. In particular, we want to be able to check automatically if a given graph property is satisfiable. Actually, in most application scenarios it is desirable to be able to explore graphs satisfying the graph property if they exist or even to get a complete and compact overview of the graphs satisfying the graph property. We show that the tableau-based reasoning method for graph properties as introduced by Lambers and Orejas paves the way for a symbolic model generation algorithm for graph properties. Graph properties are formulated in a dedicated logic making use of graphs and graph morphisms, which is equivalent to firstorder logic on graphs as introduced by Courcelle. Our parallelizable algorithm gradually generates a finite set of so-called symbolic models, where each symbolic model describes a set of finite graphs (i.e., finite models) satisfying the graph property. The set of symbolic models jointly describes all finite models for the graph property (complete) and does not describe any finite graph violating the graph property (sound). Moreover, no symbolic model is already covered by another one (compact). Finally, the algorithm is able to generate from each symbolic model a minimal finite model immediately and allows for an exploration of further finite models. The algorithm is implemented in the new tool AutoGraph.},
  language  = {en}
}
@unpublished{FishLambers2013,
  author    = {Fish, Andrew and Lambers, Leen},
  title     = {Special issue on graph transformation and visual modeling techniques - guest editors' introduction},
  series = {Journal of visual languages and computing},
  volume    = {24},
  journal   = {Journal of visual languages and computing},
  number    = {6},
  publisher = {Elsevier},
  address   = {London},
  issn      = {1045-926X},
  doi       = {10.1016/j.jvlc.2013.08.004},
  pages     = {419 -- 420},
  year      = {2013},
  language  = {en}
}
@article{LambersWeber2020,
  author    = {Lambers, Leen and Weber, Jens},
  title     = {Preface to the special issue on the 11th International Conference on Graph Transformation},
  series = {Journal of Logical and Algebraic Methods in Programming},
  volume    = {112},
  journal   = {Journal of Logical and Algebraic Methods in Programming},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {2352-2208},
  doi       = {10.1016/j.jlamp.2020.100525},
  pages     = {2},
  year      = {2020},
  abstract  = {This special issue contains extended versions of four selected papers from the 11th International Conference on Graph Transformation (ICGT 2018). The articles cover a tool for computing core graphs via SAT/SMT solvers (graph language definition), graph transformation through graph surfing in reaction systems (a new graph transformation formalism), the essence and initiality of conflicts in M-adhesive transformation systems, and a calculus of concurrent graph-rewriting processes (theory on conflicts and parallel independence).},
  language  = {en}
}
@book{BeyhlBlouinGieseetal.2016,
  author    = {Beyhl, Thomas and Blouin, Dominique and Giese, Holger and Lambers, Leen},
  title     = {On the operationalization of graph queries with generalized discrimination networks},
  number    = {106},
  publisher = {Universit{\"a}tsverlag Potsdam},
  address   = {Potsdam},
  isbn      = {978-3-86956-372-5},
  issn      = {1613-5652},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-96279},
  publisher      = {Universit{\"a}t Potsdam},
  pages     = {33},
  year      = {2016},
  abstract  = {Graph queries have lately gained increased interest due to application areas such as social networks, biological networks, or model queries. For the relational database case the relational algebra and generalized discrimination networks have been studied to find appropriate decompositions into subqueries and ordering of these subqueries for query evaluation or incremental updates of query results. For graph database queries however there is no formal underpinning yet that allows us to find such suitable operationalizations. Consequently, we suggest a simple operational concept for the decomposition of arbitrary complex queries into simpler subqueries and the ordering of these subqueries in form of generalized discrimination networks for graph queries inspired by the relational case. The approach employs graph transformation rules for the nodes of the network and thus we can employ the underlying theory. We further show that the proposed generalized discrimination networks have the same expressive power as nested graph conditions.},
  language  = {en}
}
@article{EhrigGolasHabeletal.2014,
  author    = {Ehrig, Hartmut and Golas, Ulrike and Habel, Annegret and Lambers, Leen and Orejas, Fernando},
  title     = {M-adhesive transformation systems with nested application conditions. Part 1: parallelism, concurrency and amalgamation},
  series = {Mathematical structures in computer science : a journal in the applications of categorical, algebraic and geometric methods in computer science},
  volume    = {24},
  journal   = {Mathematical structures in computer science : a journal in the applications of categorical, algebraic and geometric methods in computer science},
  number    = {4},
  publisher = {Cambridge Univ. Press},
  address   = {New York},
  issn      = {0960-1295},
  doi       = {10.1017/S0960129512000357},
  pages     = {48},
  year      = {2014},
  abstract  = {Nested application conditions generalise the well-known negative application conditions and are important for several application domains. In this paper, we present Local Church-Rosser, Parallelism, Concurrency and Amalgamation Theorems for rules with nested application conditions in the framework of M-adhesive categories, where M-adhesive categories are slightly more general than weak adhesive high-level replacement categories. Most of the proofs are based on the corresponding statements for rules without application conditions and two shift lemmas stating that nested application conditions can be shifted over morphisms and rules.},
  language  = {en}
}
@article{EhrigGolasHabeletal.2012,
  author    = {Ehrig, Hartmut and Golas, Ulrike and Habel, Annegret and Lambers, Leen and Orejas, Fernando},
  title     = {M-Adhesive Transformation Systems with Nested Application Conditions Part 2: Embedding, Critical Pairs and Local Confluence},
  series = {Fundamenta informaticae},
  volume    = {118},
  journal   = {Fundamenta informaticae},
  number    = {1-2},
  publisher = {IOS Press},
  address   = {Amsterdam},
  issn      = {0169-2968},
  doi       = {10.3233/FI-2012-705},
  pages     = {35 -- 63},
  year      = {2012},
  abstract  = {Graph transformation systems have been studied extensively and applied to several areas of computer science like formal language theory, the modeling of databases, concurrent or distributed systems, and visual, logical, and functional programming. In most kinds of applications it is necessary to have the possibility of restricting the applicability of rules. This is usually done by means of application conditions. In this paper, we continue the work of extending the fundamental theory of graph transformation to the case where rules may use arbitrary (nested) application conditions. More precisely, we generalize the Embedding theorem, and we study how local confluence can be checked in this context. In particular, we define a new notion of critical pair which allows us to formulate and prove a Local Confluence Theorem for the general case of rules with nested application conditions. All our results are presented, not for a specific class of graphs, but for any arbitrary M-adhesive category, which means that our results apply to most kinds of graphical structures. We demonstrate our theory on the modeling of an elevator control by a typed graph transformation system with positive and negative application conditions.},
  language  = {en}
}
@article{OrejasLambers2012,
  author    = {Orejas, Fernando and Lambers, Leen},
  title     = {Lazy graph transformation},
  series = {Fundamenta informaticae},
  volume    = {118},
  journal   = {Fundamenta informaticae},
  number    = {1-2},
  publisher = {IOS Press},
  address   = {Amsterdam},
  issn      = {0169-2968},
  doi       = {10.3233/FI-2012-706},
  pages     = {65 -- 96},
  year      = {2012},
  abstract  = {Applying an attributed graph transformation rule to a given object graph always implies some kind of constraint solving. In many cases, the given constraints are almost trivial to solve. For instance, this is the case when a rule describes a transformation G double right arrow H, where the attributes of H are obtained by some simple computation from the attributes of G. However there are many other cases where the constraints to solve may be not so trivial and, moreover, may have several answers. This is the case, for instance, when the transformation process includes some kind of searching. In the current approaches to attributed graph transformation these constraints must be completely solved when defining the matching of the given transformation rule. This kind of early binding is well-known from other areas of Computer Science to be inadequate. For instance, the solution chosen for the constraints associated to a given transformation step may be not fully adequate, meaning that later, in the search for a better solution, we may need to backtrack this transformation step. In this paper, based on our previous work on the use of symbolic graphs to deal with different aspects related with attributed graphs, including attributed graph transformation, we present a new approach that, based on the new notion of narrowing graph transformation rule, allows us to delay constraint solving when doing attributed graph transformation, in a way that resembles lazy computation. For this reason, we have called lazy this new kind of transformation. Moreover, we show that the approach is sound and complete with respect to standard attributed graph transformation. A running example, where a graph transformation system describes some basic operations of a travel agency, shows the practical interest of the approach.},
  language  = {en}
}
@book{DyckGieseLambers2017,
  author    = {Dyck, Johannes and Giese, Holger and Lambers, Leen},
  title     = {Automatic verification of behavior preservation at the transformation level for relational model transformation},
  number    = {112},
  publisher = {Universit{\"a}tsverlag Potsdam},
  address   = {Potsdam},
  isbn      = {978-3-86956-391-6},
  issn      = {1613-5652},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-100279},
  publisher      = {Universit{\"a}t Potsdam},
  pages     = {viii, 112},
  year      = {2017},
  abstract  = {The correctness of model transformations is a crucial element for model-driven engineering of high quality software. In particular, behavior preservation is the most important correctness property avoiding the introduction of semantic errors during the model-driven engineering process. Behavior preservation verification techniques either show that specific properties are preserved, or more generally and complex, they show some kind of behavioral equivalence or refinement between source and target model of the transformation. Both kinds of behavior preservation verification goals have been presented with automatic tool support for the instance level, i.e. for a given source and target model specified by the model transformation. However, up until now there is no automatic verification approach available at the transformation level, i.e. for all source and target models specified by the model transformation. In this report, we extend our results presented in [27] and outline a new sophisticated approach for the automatic verification of behavior preservation captured by bisimulation resp. simulation for model transformations specified by triple graph grammars and semantic definitions given by graph transformation rules. In particular, we show that the behavior preservation problem can be reduced to invariant checking for graph transformation and that the resulting checking problem can be addressed by our own invariant checker even for a complex example where a sequence chart is transformed into communicating automata. We further discuss today's limitations of invariant checking for graph transformation and motivate further lines of future work in this direction.},
  language  = {en}
}