Many problems in computer science and its applications require searching through a huge number of possible solutions. One particular challenging class of search problems is concerned with finding paths in state spaces: given a current situation A in which there are many different courses of actions we can take, how can we find a sequence of actions that takes us to a desired situation B?
One example problem of this kind is genome rearrangement: what is a minimal sequence of mutations that we would need to apply to the genome of organism X to obtain the genome of organism Y? Answering such questions is an important part of phylogenetics, the study of evolutionary relationships between organisms based on their genetic information.
In this and many other applications, we are faced with state-space search problems that are far too large to be solved by computers through simple trial-and-error. There is a need for clever search techniques that can quickly zero in on promising solutions while discarding unpromising ones. This project studies pruning techniques for problems of this kind, i.e. methods that reliably identify and discard unpromising solutions to search problems in order to avoid wasting time on their exploration.
One focus of the project is the detection and exploitation of symmetries, i.e., the identification of groups of states that are in a formal sense equivalent to each other. There is no need to consider more than one state from each group of symmetric states during search, and hence eliminating symmetric states can greatly reduce the search effort in many cases.
The second focus is on partial-order reduction, techniques that determine situations in which the order of achieving certain subproblems does not matter. When this is the case, a search method can restrict attention to only one possible order. As with symmetry elimination, partial-order reduction can greatly reduce the search effort in many cases.