You are here: TUCS > RESEARCH > Research Programmes > Combinatorics, Complex Systems and Computability (COM3)
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
Participating TUCS Research Units
Steering group
Tero Harju Iiro Honkala Juhani Karhumäki Jarkko Kari Valtteri Niemi Ion Petre Luca ZamboniActivities
- 16.–19.5.2017: Fourth Russian-Finnish Symposium on Discrete Mathematics
The topics of the symposium include, but are not restricted to,- Automata,
- Words,
- Graphs,
- Discrete dynamical systems,
- Tilings,
- Coding and informaiton theory,
The proceedings of the symposium will be published as a technical report of Turku Centre for Computer Science (TUCS). A special issue of a journal, e.g., Fundamenta Informaticae, of selected papers will be edited afterwards. - 18.11.2013: Guest Lecture: Dr. Turlough Neary (University of Zurich and ETH Zurich, Switzerland)
"The complexity of simple programs"
This talk reviews some of the simplest known universal models of computation. We discuss time complexity and program-size results for small universal Turing machines, tag systems and elementary cellular automata. For many years these systems suffered from an exponential slowdown when simulating Turing machines. We show that these models are in fact efficient (polynomial time) simulators of Turing machines. From the point of view of program-size we present a number of small universal machines for the Turing machine model, and for the weak and semi-weak variants of the model. Finally, we show that binary tag systems (a form of rewrite system with only 2 rules) are universal, and prove that the Post correspondence problem for 4 pairs of words is undecidable by reducing it to the halting problem for binary tag systems. - 9.10.2013: Guest Lecture: Abuzer Yakaryilmaz (The University of Latvia)
"Automata and complexity theory" - 23.9.2013: M. Keane (Wesleyan University): Distinguished FiDiPro lecture in Publicum, Lecture Hall 3, at 12.
"The recurrence-transience dichotomy"
In 1920, Georg Pólya taught us, in the later words of Shizuo Kakutani, that "A drunken man will eventually find his way home, but a drunken bird may be lost forever."
In more mathematical terminology, simple random walk in one or two dimensions is recurrent, but in three or more dimensions transient. When, in the well-known nursery rhyme, Gretel leaves a trail of bread crumbs to help find her way home from the forest, one would expect that her "risk-reduced" random walk is also recurrent. It is interesting that we cannot prove this yet. More puzzling yet is that in the general elementary situation, we are not sure that there is a dichotomy at all - for once reinforced random walks on locally finite connected countable graphs the possibility of partial recurrence has not yet been excluded.
In this lecture I want to try to explain possible reasons for the behaviour Pólya discovered, at a leisurely pace, and the conjectures, now over twenty years old, concerning reinforced random walks on ladders. I'll finish then, time permitting, with a new dichotomy conjecture which, if true, would allow us to classify graphs into recurrent and transient ones. - 24.–26.9.2013: M. Keane (Wesleyan University): TUCS Short Course
"Topics in ergodic theory" in Publicum, seminar room of psychology (second floor), at 14. - 27.9.2013: Guest lecture: M. Volkov (Ural Federal University, Ekaterinburg) in Publicum, seminar room of psychology, at 10.
- 4.6.2013: Guest lecture: Solomon Marcus
Going Beyond
Trying to go beyond classical logic, Archimedes axiom, Fifth Postulate in Euclid’s Elements, the Galileo-Newtonian representation of phenomena related to time and energy, the macroscopic universe, the choice axiom, von Neumann’s axiom of foundation, continuum hypothesis, Turing’s computability, the field of competence of human language and human semiosis, the representation of artistic beauty as based on order, simplicity, harmony and symmetry means to transgress the borders of the common perception of the world according to our senses. We try to obtain the picture of these enterprises and to point out their meaning and their relevance, as components of a new, anti intuitive world emerging in the last decades. In a second step, we try to bridge this view with another one, coming from the way transcendence is emerging in mathematics, logic, music, philosophy.
Host: Ion Petre - 4.10.2012: FiDiPro distinguished lecture: Aldo de Luca
A palindromization map on free monoids and its generalizations
This talk is a survey of several results of combinatorial nature which have been obtained starting from a palindromization map ψ on a free monoid A* introduced by the author in 1997 in the case of a binary alphabet, and successively generalized by other authors for arbitrary finite alphabets. If one extends the action of the palindomization map to infinite words, one can generate the class of all standard episturmian words, introduced by Droubay, Justin and Pirillo in 2001, which includes standard Sturmian words and Arnoux-Rauzy words. A noteworthy generalization of the palindromization map is obtained starting with a given code X over A. The new operator ψX maps X* to the set of palindromes of A*; some properties of ψ are lost and some are saved in a weak form. When X has a finite deciphering delay one can extend ψX to Xω, generating a class of infinite words much wider than standard episturmian words. For a finite and maximal code X over A, a suitable generalization of standard Arnoux-Rauzy words is obtained. Finally, one can generalize further ψX by replacing palindromic closure with ϑ-palindromic closure, where ϑ is any involuntory antimorphism of A*. This yields an extension of the class of ϑ-standard words introduced by the author and Alessandro De Luca in 2006.
Host: Juhani Karhumäki - 2.10.2012: guest lecture: Academician Yuri Matiyasevich (Steklov Institute of Mathematics, St. Petersburg, Russia)
Calculating approximate values of zeros of Riemann's zeta function via interpolating determinants
Abstract in http://logic.pdmi.ras.ru/~yumat/personaljournal/artlessmethod/artlessmethod.php
Host: Juhani Karhumäki - 25.–28.9.2012: RuFiDiM 2012 – Russian Finnish Symposium on Discrete Mathematics
The second RuFiDiM conference, Russian-Finnish Symposium in Discrete Mathematics, took place in Turku on September 25th to 28th, 2012. The meeting was organized as a part of the research activities in the framework of cooperation between Russian Academy of Sciences and the Academy of Finland. The cooperation is between the Steklov Institute of Mathematics at St. Petersburg and FUNDIM Centre at University of Turku. The goal of the series of these symposiums is to increase cooperation between Finnish and Russian mathematicians in discrete mathematics, but the symposium is open for a broader international audience. Indeed, in the present event there were contributions from over 10 different nations.RuFiDiM 2012 consisted of six invited talks and 31 contributed presentations. The program was chosen by an international program committee. Abstracts/extended abstracts of the lectures are presented in these proceedings.
Host: Juhani Karhumäki, Yuri Matiyasevich - 7.8.2012: guest talk: Dr. Mathieu Sablik (Aix-Marseille Universite, France)
Which measure can be obtained as limit of an iteration of a measure by a cellular automaton?
A computable measure iterated by a cellular automaton stay computable. Thus the limit of an iteration of a measure by a cellular automaton is a semi-computable measure, that is to say that we can approximate this measure with a Turing machine without necessary know the rate of the approximation. In this talk we show that in fact all such measure can be obtained by a cellular automaton starting from an ergodic measure of full support. Better, we can construct a "metrical universal cellular automaton" in the sense that for this cellular automata, every semi-computable measure can be obtained following the initial measure chosen.
Host: Jarkko Kari - 8.6.2012: guest talk: Dr. Igor Potapov (University of Liverpool, UK)
Computational Complexity of Identity Problem for Words and Matrices
Most computational problems for matrix semigroups and groups are inherently difficult to solve and in many cases can even be impossible, due to a number of undecidability results which have been shown for high dimensional matrices. Some examples of such problems are the membership problem (including the special cases of the mortality and identity problems), vector reachability, freeness problems and emptiness of semigroup intersections.
There are various techniques and methods for embedding universal computation into three and four dimensional matrix semigroups. In particular, in dimension three, problems such as membership, vector reachability and freeness are undecidable for integral matrices.
In this talk several closely related fundamental problems for words and matrices will be considered. First, we introduce the Identity Correspondence Problem (ICP): whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. We prove that ICP is undecidable by a reduction of Post's Correspondence Problem via several new encoding techniques. Then we use ICP to answer a long standing open problem concerning matrix semigroups: "Is it decidable for a finitely generated semigroup $S$ of integral square matrices whether or not the identity matrix belongs to $S$?". Also we investigate the complexity status of the Identity Problem for 2x2 matrix semigroups and a lower bound on the minimum length solution to the Identity Problem for a constructible set of instances, which is shown to be exponential.
Host: Mika Hirvensalo - 4.6.2012: guest talk: Academician Solomon Marcus (Academy of Romania)
From Turing to Von Neumann
They interacted and inspired each other. We focus main attention on their work on the brain and, more generally, on their interest in biology, trying to situate historically and conceptually John von Neumann's unfinished research program towards the unification of discrete and continuous involvement of mathematics in the study of biological systems. Turing was involved in a similar program. An evolutionary trajectory of theories from Leibniz, Boole, Bohr and Turing to Shannon, McCullogh-Pitts, Wiener and von Neumann powered the emergence of the information paradigm. As both Turing and von Neumann were interested in automata, they were deeply challenged by seeing the brain as an automaton. Turing's research was done in the context of the achievements in logic (formalism, intuitionism, logicism, constructivism, Hilbert's, Kleene's and Gödel's work). Turing's 1937 paper, proposing a theoretical machine exclusively built on the paper, has been the preliminary theoretical step towards von Neumann's 1948 programmable electronic computer. John von Neumann's research program is outlined in "The general and logical theory of automata" (1951), "Probabilistic logics and the synthesis of reliable organisms from unreliable components" (1956) and his posthumous book The Computer and the Brain (1958) and in his unfinished book The theory of Self-Reproducing Automata, completed and published by A. Burks (1966).
Inspired by Turing's universal machine, von Neumann described in 1948, i.e., five years before Watson and Crick, the structure of the DNA copying mechanism for biological self-reproduction. A lot of questions and problems appear when confronting these historical facts with the evolution of ideas in the contemporary fields of computational biology and biological computing. Some of them are pointed out in this presentation.
Host: Juhani Karhumäki, Ion Petre - 31.5.2012: guest talk: Artur Jez
Fully compressed pattern matching by recompression
In this talk I will consider the a fully compressed pattern matching problem. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string; the term fully means that both the pattern and the text are given in the compressed form. The problem is approached using a recently developed technique of local recompression: the SLPs are refactored, so that subwords of the pattern and text are encoded in both SLPs in the same way. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Thus, in the end, the pattern matching reduces to a search of a particular nonterminal in the derivation tree for the text.
This technique yields an O((n+m) log M) algorithm for compressed pattern matching, where n (m) is the size of the compressed representation of the text (pattern, respectively), while M is the size of the decompressed pattern. Since M is at most 2^m, this substantially improves the previously best O(m^2n) algorithm.
Since LZ compression standard reduces to SLP with log( N / n) overhead and in O(n log(N/n)) time (where N is the size of the decompressed text and n the size of the LZ representation), the presented algorithm can be applied also to the fully LZ-compressed pattern matching problem, yielding an O((n log(N/n) + m log(M/m)) log M) running time.
Host: Juhani Karhumäki
Mailing list
Click here to subscribe to the Com3 announcements mailing list.