Faculty of Informatics Vienna University of Technology Institute of Computer Aided Automation PRIP Home PRIP Home
Personal tools
You are here: Home People Yll Haxhimusa, Dipl.-Ing. Dr. techn. Dagstuhl Seminar 11351

Dagstuhl Seminar 11351

Dagstuhl Seminar

Computer Science & Problem Solving: New Foundations

Dagstuhl Seminar Number 11351

Date: 28.08.2011 - 02.09.2011

Download the flyer of the Seminar.


Iris van Rooij, Radboud University, The Netherlands
Yll Haxhimusa, Vienna University of Technology, Austria
Georg Gottlob, Oxford University, UK
Zygmunt Pizlo, Purdue University, USA



Computer science has played a defining role in laying the foundations for cognitive psychology in the 1950s. Theories of computing at that time have had major impact on how psychologists have conceptualized the cognitive processes underlying human problem solving (e.g., through the seminal work of Allen Newell and Herbert Simon), and this impact continues even to this day. Yet, recent developments in problem solving research have also unveiled some limitations of classical approaches to problem solving and it seems that fundamentally new computational ideas are needed in order to move the field of problem solving forward. For instance, the classical idea of ‘problem solving as search through a search space’ can perhaps explain the difficulty of some problems (e.g., problems that are hard because they have intrinsically complex search spaces, such as NP-hard problems), but it seems unable to explain the difficulty of a whole class of other important problems (e.g., problems for which ‘solving’ means ‘correctly representing’). For the latter class of problems, once the right representation has been formed, solving the problem is easy. This observation raises several questions:

1. How can we explain the process of building up a problem representation? Can we explain it computationally?
2. Can we explain why, and predict when, finding the right representation is difficult, and when it is easy?
3. Can we build a computational theory for different classes of ‘representational complexity’, analogous to existing classes of ‘computational complexity’?
4. Can the notions of computational complexity and representational complexity possibly be reconciled by a unifying theory of problem solving?

There are many different ways to approach the notion of ‘representational complexity’. One idea is that a problem is difficult if the problem solver unintentionally has settled on a wrong representation and is unaware of this or otherwise unable to let go of the wrong representation in order to find a better one (the notion of ‘fixedness’ in cognitive psychology expresses this idea). Another idea is that a problem is difficult if the problem solver knows that the current representation is faulty, but finding a better representation requires (potentially sequentially) choosing from a (potential indefinite) set of re-representation operators (this idea is pursued in the domain of analogical problem solving). Yet, another idea is that a problem is difficult if it does not allow for a representation that affords efficient search of the problem space (this idea has connections to theories of data structures and their relationship with computational efficiency).

This seminar aims to bring together computer scientists and psychologists to exchange ideas, models and experimental data on human and artificial problem solving. The primary aim of the seminar is to inspire new formal approaches to ‘representational complexity’ and to build a research agenda for advancing our understanding of the role of ‘representation’ in human and artificial problem solving. Attendees are invited to present their own research and explore opportunities for new collaborations. After the completion of the seminar, all participants will be invited to submit their presented work for publication in a special issue of the Journal of Problem Solving (http://docs.lib.purdue.edu/jps/).

The seminar welcomes researchers from a wide variety of research areas, including, but not limited to, the following.


Computer science:graph theory, topology, geometry, logic, computational complexity, descriptive complexity

Psychology: cognitive modeling, heuristics, insight, visual problem solving, analogical problem solving, creativity, education.

List of Participants:

  1. Aouada, Djamila
  2. Bajcsy, Ruzena
  3. Batchelder, William H.
  4. Bauckhage, Christian
  5. Blokpoel, Mark
  6. Carruthers, Sarah
  7. Chu, Yun
  8. Dechter, Rina
  9. Filder, Sanja
  10. Forbus, Kenneth D.
  11. Gabora, Liane
  12. Gentner, Dedre
  13. Goodman, Noah D.
  14. Gottlob, Georg
  15. Grzegorzek, Marcin
  16. Haxhimusa, Yll
  17. Hedrich, Jens
  18. Ion, Adrian
  19. Juba, Brendan
  20. Kanj, Iyad
  21. Knauff, Markus
  22. Kropatsch, Walter
  23. Kwisthout, Johan
  24. Landy, David
  25. MacGregor, James N.
  26. Miklos, Zoltan
  27. Musliu, Nyrset
  28. Pizlo, Zygmunt
  29. Stege, Ulrike
  30. Szymanik, Jakub
  31. Taatgen, Niels A.
  32. Tak, Susanne
  33. Tsotsos, John K.
  34. Varma, Sashank
  35. Wagenmakers, Eric-Jan
  36. Wareham, H. Todd
  37. van Dijk, Jelle
  38. van Rooij, Iris