Externe zielgerichtete Suche in impliziten Graphen

• Applicant: Professor Dr. Bernhard Steffen, since 4/2008
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 49332706

In this project we aim at advances of dictionary data structures in the context of states space search with applications in AI, model checking and beyond. In large state spaces, efficient dictionary data structures are crucial for the success of search algorithms. Among them, priority queues to maintain the set of states to be expanded and hash tables for storing all visited states are most important. Additionally, we find dictionaries based on BDDs for maintaining sets of states compactly and generalized suffix trees to prune forbidden state sequences, as well as pattern databases for computing lower bounds. By the tremendous sizes of the state spaces in the application domains, the search challenges compuational resources. Systems of hard disks are used in specialized algorithms to overcome limitations in main memory. Then, the performance bottleneck again is processing speed, so that many cores are required to realize dictionaries with concurrent access. Moreover, solutions designed for dealing with explicit graphs are not always applicable when dealing with implicit state spaces.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering
• Ehemaliger Antragsteller: Professor Dr. Stefan Edelkamp, until 4/2008