Where academic tradition
meets the exciting future

Com3 – Combinatorics, Complex Systems and Computability

Research area

This research programme ties together several related projects in discrete mathematics and theory of computation. The involved projects investigate combinatorics on words, coding theory, cryptography, automata theory, cellular automata, unconventional computation, tilings and symbolic dynamics. A common theme is the discreteness of the studied objects, which leads to the employment of combinatorial methods. Computability aspects are also central in many of the projects.

Combinatorics is heavily used in the research of coding theory (Iiro Honkala’s group) and cryptography (Valtteri Niemi’s group). Combinatorics on words (Juhani Karhumäki, Tero Harju, and their groups) concerns the structure of finite or infinite sequences of symbols, in one or more dimensions. The topic of complexity and combinatorics of infinite words is investigated also by the FiDiPro group, led by Luca Zamboni. In the spirit of symbolic dynamics, infinite words can be seen to model complex dynamical systems. Much can be said concerning global regularities that arise from local rules on the words. Multidimensional words are related to tilings and cellular automata, studied by Jarkko Kari and his group. In higher dimensions, simple tiling systems become computationally universal, and computability questions become central. Cellular automata and tilings are archetypical examples of discrete complex systems with simple individual components but complex overall behaviour. Tiling systems provide an expressive model of self-assembly, capable of producing complex structures found in nature. Cellular automata and tilings constitute unconventional methods to perform computation. Other such methods include biologically inspired computational models, studied by Ion Petre and his group. Biological systems provide a fascinating example of global complexity arising from simple local behaviour. They are a rich source of inspiration for new models of computing, including DNA-based computing, molecular self-assembly, computing through gene assembly, and computing through reaction and membrane systems.

Research goal

The goal of the research programme is to increase our understanding of complexity and the relationship between local and global structures in discrete systems and models, may it be a communications network, a biological system, or an abstraction such as a cellular automaton or simply a sequence or an array of symbols. Understanding the emergence of complex behaviour and the computational capabilities in large systems consisting of very simple interacting components is of particular interest. The programme also investigates algorithmic questions concerning such systems. One frequently encounters uncomputability, and in many instances the aim is to clarify the borderline between decidable and undecidable. Specific research problems can be found in the research statements of the participating groups.

Programme leader

Jarkko Kari

Participating TUCS Research Units

Steering group

Tero Harju Iiro Honkala Juhani Karhumäki Jarkko Kari Valtteri Niemi Ion Petre Luca Zamboni


Mailing list

Click here to subscribe to the Com3 announcements mailing list.