Author: Vesa Halava

Time: 4.5.2021 at 13:00

Speaker: Alexander Tiskin, St Petersburg University

Title: The surprising algebra of string comparison

Abstract:We consider the classical Longest Common Subsequence (LCS) problem on a pair of strings, also known as the Sequence Alignment problem in bioinformatics. The textbook solution for this problem is based on dynamic programming, and seems to be the only possible. We will show that this is not the case: a suitably generalised version of the LCS problem can be solved efficiently by a divide-and-conquer algorithm. In this alternative solution, subproblems are combined using a seemingly unrelated structure, known as the Hecke (or “sticky braid”) monoid, which can be defined via tropical matrix multiplication, and bears a close resemblance with the classical braid group. Such an approach is not only of theoretical interest, but also allows us to obtain efficient algorithms for approximate pattern matching on compressed strings without decompression, parallel string comparison, the maximum clique problem on circle graphs, as well as some real-life bioinformatics problems.

Time: 9.3.2021 13:00

Speaker: Esa Sahla, University of Turku

Title: Self-shuffles with substitutions

Abstract: In formal language theory the operation of shuffling has been an occurring concept for over half a century. The operation has been studied in the context of formal languages as well as computability and process algebras. In this talk we will present some basic results on word shuffling with emphasis on shuffling a word with itself, i.e. the self-shuffle. We will then focus on a variant of the self-shuffle where a word is shuffled with its image under a letter-to-letter substitution. We will show that for a given regular language R it is undecidable whether there exists a word such that the forementioned self-shuffle intersects with R. The problem is reduced to the Post Correspondence Problem with a brief overview of PCP itself.

Time: 15.12.2020 13:00

Speaker: Toni Hotanen, University of Turku

Title: Lyapunov Exponents and Topological Entropy of Cellular Automata and Turing Machines

Abstract: Lyapunov exponents are an important concept in differentiable dynamical systems and they measure stability or sensitivity in the system. Their analogues for cellular automata were proposed by Shereshevsky and since then they have been further developed and studied. It was conjectured that there does not exist such a sensitive cellular automaton, that would have both the right and the left pointwise Lyapunov exponents taking the value zero, for each configuration. In this talk we prove the conjecture false by constructing such a cellular automaton, using aperiodic, complete Turing machines as a building block. In the second part of the talk we will work on several related decision problems in the setting of reversible Turing machines and cellular automata. The decision problems we are interested in are related to the notions of periodicity, topological entropy, speed and Lyapunov exponents. We will prove several of these problems to be undecidable in the setting of reversible Turing machines and as a corollary we get analogous results in the setting of reversible cellular automata.

Time: 3.11.2020, 13.00

Speaker: Professor Jöel Ouaknine from  MPI for Software Systems (Germany) and  University of Oxford (UK)

Title: Holonomic Techniques, Periods, and Decision Problems

Abstract: Holonomic techniques have deep roots going back to Wallis, Euler, and Gauss, and have evolved in modern times as an important subfield of computer algebra, thanks in large part to the work of Zeilberger and others over the past three decades. In this talk, I will give an overview of the area, and in particular will present a select survey of known and original results on decision problems for holonomic sequences and functions. I will also discuss some surprising connections to the theory of periods and exponential periods, which are classical objects of study in algebraic geometry and number theory; in particular, I will relate the decidability of certain decision problems for holonomic sequences to deep conjectures about periods and exponential periods, notably those due to Kontsevich and Zagier.

Parts of this talk will be based on the paper “On Positivity and Minimality for Second-Order Holonomic Sequences”, https://arxiv.org/abs/2007.12282