Effective Complexity of Stationary Process Realisations

The concept of effective complexity of an entity as the minimal description length of its regularities has been initiated by Gell-Mann and Lloyd. In the talk we present a proposal for a precise definition of effective complexity of finite binary sequences. We discuss shortly its basic properties as well as its relation to other complexity measures, e.g. Kolmogorov complexity, Bennett's logical depth and Kolmogorov minimal statistics. We analyse the effective complexity of long typical realisations of stationary processes. Based on this analysis, we address the question to what extent our results imply limitations of the concept.