Course "Combinatorics of words and its applications"

Each university is faced with the fact that it is impossible to find a teacher on some topics in the city who would be a specialist in this topic. One of the options to solve this problem is to entrust the preparation of a course on this topic to some of the available teachers who are not experts in this field. We at the Akadeic University are trying to go the other way - to invite a specialist to read the course. Last year, we participated in the competition of the Dynasty Foundation “guest professor”. We submitted two applications and both won, as well as two of our teachers were invited to the Ural and Kazan Federal Universities. In September 2014, Alexander Okhotin from the University of Turku read the Formal Grammar course. And on March 18, Arseny Mikhailovich Shur, a professor at the Ural Federal University, will start reading the course “Combinatorics of Words and Its Applications”. We decided to make this course completely open to everyone and to conduct it within the Computer Science Club, our permanent partner.

Arseny Mikhailovich is an active researcher in the field of combinatorial words, so the course promises to be very interesting. The first lesson will be held on Wednesday, March 18 at 18-30 in the Marble Hall of POMI RAS (St. Petersburg, Fontanka Embankment, 27), admission is free, registration is not required.

Detailed course description and schedule: here .
')
Brief course description


Symbolic sequences (words), which are the main object of research of combinatorics of words, surround us everywhere. These are lexemes, phrases and texts in natural languages, source codes of programs and libraries, server logs and data exchange protocols, mathematical and chemical formulas, DNA molecules and proteins, symbolic trajectories of points in phase space, number entries in a positional number system, and much more. To work effectively with such an abundance and variety of words, an appropriate mathematical apparatus is needed, which is provided by combinatorics of words. The origin of the combinatorics of words is associated with the outstanding works of the Norwegian mathematician A. Thue (1863-1922) about non-repetitive words. The design of combinatorial words as an independent discipline occurred in the early 1980s, when a group of French mathematicians under the leadership of M. Schützenberger wrote the book Combinatorics on words in the framework of the Encyclopedia of Mathematics and Its Applications project. Currently, word combinatorics is a dynamically developing discipline at the intersection of discrete mathematics and computer science. As part of the training course, it is impossible to state the entire scientific discipline, so our main goal is to give students an idea of ​​the main features of words and how and why you need to study words (including infinite, cyclic and partial). Much attention in the course is paid to the connections of “internal” objects and results with “external” statements of problems from various branches of mathematics and computer science. The course material is grouped around the following properties and concepts:

• non-commutative multiplication of words and its consequences;
• lexicographical order in words, its properties and use;
• repetitions in words: periods and properties of periodic words, squares, palindromes;
• non-repetition and other avoidance options;
• word counting functions;
• codes and coding (if we have time).