Program
Symposium starts early in the morning on September 21
- invited lectures 60 minutes
- contributed talks 30 minutes
- student talks 20 minutses
- 09:00 09:45 Registration
- 09:45 10:00 Opening
- 10:00 11:00 Invited lecture
Dima Grigoriev (Lille, France) Complexity of solving tropical linear systems and conjecture on a tropical effective Nullstellensatz.
- 11:00 11:20 Coffee break
- 11:20 11:50 Contributed talk
Svetlana Puzynina (Univ. of Turku)
On some new abelian properties of infinite words.
- 11:50 12:10 Short Communication
Turo Sallinen (Univ. of Turku)
Function and Image Manipulation with Automata.
- 12:10 14:00 Lunch
- 14:00 15:00 Invited lecture
Alexander Ivanov (Imperial College London )
Current Progress in Majorana Theory
- 15:00 15:30 Contributed talk
S. A. Obraztsova, A. V. Pastor (Steklov Institute, St. Petersburg)
About vertices of degree k of minimally and contraction critically k-connected graphs: upper bounds - 15:30 15:50 Coffee break
- 15:50 16:20 Contributed talk
Dmitry V. Chistikov (Moscow State Univ.)
Using Relevance Queries for Identification of Read-Once Functions.
- 16:20 16:40 Short Communication
Ivan Burmistrov, Lesha Khvorost (Ural State Univ., Ekaterinburg)
Straight-line Programs: A Practical Test.
- 16:40 17:00 Coffee break
- 17:00 17:30 Contributed talk
Alica Kelemenova (Silesian Univ., Opava)
Complementary Reset Words Problem.
- 17:30 17:50 Short Communication
A. V. Bankevich (Steklov Institute, St. Petersburg)
Bounds of a number of leafs of spanning trees in graphs without triangles.
- 18:00 Welcome Party
- 09:00 10:00 Invited lecture
Mikhail Volkov (Ural State University)
Exponent sequences of labeled digraph vs reset thresholds of synchronizing automata.
- 10:00 10:30 Contributed talk
Juhani Karhumaki, Aleksi Saarela (Univ. of Turku)
On Maximal Chains of Systems of Word Equations.
- 10:30 10:50 Coffee break
- 10:50 11:20 Contributed talk
S. Nikolenko (Steklov Institute, St. Petersburg)
A group-based combinatorial complete one-way function.
- 11:20 11:50 Contributed talk
M. Bucci, A. De Luca, L. Q. Zamboni (Univ. of Turku)
Reversible Christoffel factorizations.
- 11:50 12:10 Short Communication
Alexey V. Samsonov, Arseny M. Shur (Ural State Univ., Ekaterinburg)
On Abelian Repetition Threshold.
- 12:10 14:00 Lunch
- 14:00 15:00 Invited lecture
Luca Zamboni (Univ. of Lyon and Univ. of Turku)
Ramsey theory and Sturmian partitions.
- 15:00 15:30 Contributed talk
Aleksi Saarela (Univ. of Turku)
Word Equations and Linear Algebra.
- 15:30 15:50 Coffee break
- 15:50 16:20 Contributed talk
Anna Frid (Sobolev Institute, Novosibirsk)
On complexity of quadratic permutations
- 16:20 16:50 Contributed talk
V. A. Baransky, T. A. Senchonok (Ural State Univ., Ekaterinburg)
Chromatic uniqueness of elements of height 3 in lattices of complete multipartite graphs.
- 16:50 17:10 Short Communication
Marina I. Maslennikova (Ural State Univ., Ekaterinburg)
Reset Complexity of Ideal Languages
- 17:10 17:30 Coffee break
- 17:30 18:00 Contributed talk
P. V. Martyugin (Ural State Univ., Ekaterinburg)
Synchronization of automata with one undefined or ambiguous transition.
- 18:00 18:20 Short Communication
D. S. Ananichev, D. D. Dublennykh (Ural State Univ., Ekaterinburg)
Lower bounds for the number of keys in Zakrevskij cipher.
Friday, September 23
- 09:00 10:00 Invited lecture
Il'ya Ponomarenko (Steklov Institute, St. Petersburg)
Recognizing and isomorphism testing schurian tournaments in polynomial time
- 10:00 10:30 Contributed talk
M.Vsemirnov (Steklov Institute, St. Petersburg)
Lower bounds for weakly k-min-wise independent families of permutations.
- 10:30 10:50 Short Communication
Elena A. Petrova, Arseny M. Shur (Ural State Univ., Ekaterinburg)
Constructing Premaximal Binary Cube-free Words of Any Level.
- 10:50 11:10 Coffee break
- 11:10 11:40 Contributed talk
Edward A. Hirsch, Dmitry Itsykson (Steklov Institute, St. Petersburg)
On an optimal randomized acceptor for graph nonisomorphism.
- 11:40 12:10 Contributed talk
Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal (Steklov Institute, St. Petersburg)
Optimal heuristic algorithms for the image of an injective function.
- 12:10 12:30 Short Communication
G. V. Nenashev (Steklov Institute, St. Petersburg)
An upper bound on the chromatic number of circle graphs without K4
- 12:30 14:20 Lunch
- 14:20 15:20 Invited lecture
Tero Laihonen (University of Turku)
Identifying codes in graphs: a special class of dominating sets
- 15:20 15:50 Contributed talk
Sandrine Julia (Univ. of Nice, Sophia Antipos)
Minimal uncompletable words.
- 15:50 16:10 Coffee break
- 16:10 16:40 Contributed talk
Mika Hirvensalo (Univ. of Turku)
A Method for Computing the Characteristic Polynomial and Determining Semidefiniteness.
- 16:40 17:10 Contributed talk
D. V. Karpov (Steklov Institute, St. Petersburg)
Dynamic proper vertex colorings of a graph.
-
17:10 17:30 Short Communication
Evgeny Skvortsov, Yulia Zaks (Ural State Univ., Ekaterinburg)
Synchronizing random automata on 4-letter alphabet.
- 17:30 17:50 Short Communication
Mari Huova, Juhani Karhumaki (Univ. of Turku)
Observations and Problems on k-abelian avoidability.
- 17:50 18:00
- 18:00 21:00 Party
Saturday, September 24
- 09:00 09:30 Contributed talk
Alexander Okhotin (Univ. of Turku)
Formal grammars: reappraising the foundations.
- 09:30 10:00 Contributed talk
Tomas Hejda, Zuzana Masakova, Edita Pelantova (Czech Technical Univ., Prague)
Dynamical systems generating the extremal representations in a negative base.
- 10:00 10:20 Short Communication
A. L. Glazman (Steklov Institute, St. Petersburg)
Generalized flowers in k-connected graphs.
Application to the case k = 4.
- 10:20 10:40 Coffee break
- 10:40 11:10 Contributed talk
Dexter Kozen (Cornell Univ.), Alexandra Silva (Radboud University, Nijmegen)
On Moessner’s Theorem.
- 11:10 11:40 Contributed talk
Mikhail V. Berlinkov (Ural State Univ., Ekaterinburg)
Some Methods Related to the Cerny Conjecture.
- 11:40 12:00 Short Communication
Dmitry Itsykson, Dmitry Sokolov (Steklov Institute, St. Petersburg)
Lower bounds for myopic DPLL algorithms with a cut heuristic.
- 12:00 13:50 Lunch
- 14:30 16:30 Boat excursion
Wednesday, September 21
Thursday, September 22