Available Project Proposals
For background information on the topic as a whole, scroll to the end of this page.
If you are interested in the general topic, or if you have your own project idea related to the topic, please contact us directly. Alternatively, you can also work on one of the following concrete project proposals:
Complexity metrics on graph models (Milan Lopuhaä-Zwakenberg) Contact: Milan Lopuhaä-Zwakenberg
Graphs are an essential tool for modeling high-tech systems. The complexity of a graph can be measured in many ways, from simple metrics like the number of nodes and edges, to more complicated ones such as algebraic connectivity and treewidth. The goal of this project is to study which complexity metrics are relevant in modeling: What do measure, and how easy are they to compute? And does a metric actually tell us what we want to know?
Although no company is involved, it is possible to devote (part of) the project to a case study such as Facebook or the Dutch railway system.
From Term Rewriting to Graph Rewriting: Building a Bridge between Maude and GROOVE (Arend Rensink) Supervisor: Arend Rensink
Term Rewriting and Graph Rewriting are rule-based modelling formalisms, both with solid theoretical foundations and relatively mature tool support. Both can be used to specify system behaviour, in a similart way: the initial and subsequent system states are captured by structures that can be modified (rewritten) by rules. The main difference lies in the nature of those structures, which (as the names imply) are syntactical terms in one case, and graphs in the other.
In a strict sense, terms can be seen as (syntax) trees, which are themselves special cases of graphs; in that sense, graph rewriting is the more general and hence more powerful of the two. As usual, however, generality comes at a price, in this case involving the complexity of rule application: term rewriting is potentially more efficient than graph rewriting. However, how large the difference is for practical purposes is less evident.
In this project, the relation between term rewriting and graph rewriting is investigated on a practical level, namely by implementation a translation from specifications in Maude, a term rewriting tool, to specifications in GROOVE, a graph rewriting tool, and comparing the performance of the two tools on the basis of a set of case studies. The implementation should be based on a semantically sound transformation between the formalisms. Thus, the outcome of the project should be:
- A theoretical basis for the transformation of term rewrite rules to graph rewrite rules
- An implementation of this transformation from Maude format to GROOVE format
- A set of experiments on the basis of existing Maude models, showing the relative performance of the two
References
Heuristics for graph problems (Milan Lopuhaä-Zwakenberg) Contact: Milan Lopuhaä-Zwakenberg
If you have your own proposal related to heuristics for graph problems, please contact me to discuss the opportunities. The general approach is to study an NP-hard graph problem of your choice and develop heuristics for finding good solutions.
In addition, graph transformation is one of the techniques for model transformation; project proposals that focus on this application can be found in the topic of Software Engineering.
Contact
Background
Graphs can be used as effective models in a very diverse range of domains, within and without computer science. When used as such, they form an appealing and intuitive abstraction in which only the essentials of the domain are represented. Based on graph models, their analysis, their transformation and their evolution over time, understanding of and predictions about the systems being modelled ensue.
The topic of graphs leads to projects of varying nature, ranging from theoretical (the study of graph properties and the mechanics of graph transformation) and application-oriented (developing graph-based models for a particular domain, be it chemical, physical, or digital) to implementation (designing and implementing particular analyses or search strategies).
Related Courses
- Graph Transformations (202100114)
- Graph Algorithms and Complexity (201900082)
- Graph Theory (191520751)
