Abstract

Today's ubiquity of information poses some deep scientific problems---as there are many aspects to the functioning of meaningful information that we do not understand very well. I have long been interested in the following aspect, which one runs up against in every meaningful cognitive task: on the one hand, we want information structures that are rich in expressive power---but on the other, these structures need to be manipulated by cognitive/computational processes that consume bounded algorithmic resources. There is an inevitable tension between informational expressiveness and computational complexity. Rich representation structures are hard to manipulate, fast processes can only handle relatively shallow information structures. The big challenge is to understand the balance between expressive power and computational complexity, looking for logical architectures that represent some optimum.

In my talk I will discuss work aimed at analyzing this balance, from a logical point of view, and at developing systematic ways of observing the interplay. To maintain focus, two choices will be made: I will choose one particular logical stance, viz. so-called restricted description languages, and I will choose one type of application, viz. accessing information, both as it occurs with humans and in IT tasks.

As will become clear during the talk, understanding the balance between expressive power and algorithmic complexity calls for a mixture of foundational, experimental, and interdisciplinary work.