There are many different methods which contribute to improving software quality. They range from requirement techniques, architecture design, specification languages and programming languages to testing and program verification techniques. Such methods are often specific to a programming paradigm. Rule-based programming and high-level replacement systems constitute one of the most promising abstract programming paradigms. The merits of string and term rewriting are well known, in particular when it comes to applying verification techniques. However, several real-life problems cannot be encoded easily by means of trees but need more powerful structures such as graphs. Graphs are actually common mathematical structures which are visual and intuitive. They constitute a natural and high-level way for system modeling in several areas of science including computer science (such as Model Driven Engineering and security analysis), life sciences, business processes, etc. The goal of the project Climt consists in developing new very high level frameworks to formally design and prove rule-based programs which handle complex structures modeled as graphs.