XX

Mons Theoretical
Computer Science Days

Naples, Italy, 7-10 Sep. 2026

The conference

The 20th edition of Mons Theoretical Computer Science Days (Journées montoises d'informatique théorique) will be held at University of Naples Federico II from September 7 (afternoon) to 10 (morning), 2026. As in previous editions, these days will feature invited talks and selected talks based on abstracts.

The main themes of the conference are combinatorics and algorithms on words, theory of automata and formal languages, discrete dynamical systems and symbolic dynamics, logic and formal methods.

It also welcomes other branches of theoretical computer science and discrete mathematics related to these fields (number theory, computability, semi-groups, tilings, game theory, discrete geometry, bioinformatics, etc.).

The official languages of the conference are English and French.

Venue

Università degli Studi di Napoli Federico II

Scuola Politecnica e delle Scienze di Base

Piazzale Tecchio, 80

Naples, Italy

Google Maps

Registration

A registration fee is required for participation, as shown below. At least one registration is required per accepted abstract.

To be eligible for the student fees it is required to be enrolled as a bachelor/master/PhD student at the time of the registration.

The fee includes at least the conference materials, all coffee breaks, and the conference banquet. It should be paid by bank transfer, following the instructions below; please note that after August 28, only on site registration in cash upon arrival will be possible.

To complete the registration, it is required to send an email to jm26@easychair.org with proof of the bank transfer attached, including the following information: full name, affiliation, talk title (if any), dates of arrival/departure (if known), and any dietary restrictions or specific requirements.

Important dates

Abstract submission (EXTENDED): May 29 June 10, 2026, AoE

Notification of acceptance: July 3, 2026

End of early bird registration: July 17, 2026

Conference start: September 7, 2026 (afternoon)

Conference end: September 10, 2026 (morning)

Invited talks

Pamela FLEISCHMANN (Kiel, Germany)

Title: Scattered Factor Universality - A Survey

Abstract: Since the seminal work of Imre Simon in the 1970s, a lot of research time has been invested into scattered factors (also known as subsequences or scattered subwords). A scattered factor is a non-necessarily consecutive part a word but in correct order, e.g., mai and rade are scattered factors of normandie but monde is not since the o occurs before the m. Within the last 50 years, the main question by Simon about the index of the nowadays called Simon congruence relation is still open: two words are called k-Simon congruent if they have exactly the same scattered factors up to length k. For instance, the words abab and abba are 2-Simon-congruent but not 3-Simon-congruent. Thus, the research in the field around scattered factors has broadened in order to find an angle to tackle Simon’s original problem.

Toghrul KARIMOV (Saarbrücken, Germany)
Title: Preservation theorems for transducer outputs

Abstract: Suppose we have a deterministic finite-state transducer A and an infinite word x, and run A on x to obtain an infinite word A(x). Which properties of x are guaranteed to also hold for A(x)? We will discuss this preservation question for various well-known combinatorial properties, e.g., recurrence, being morphic, and having factor frequencies. The celebrated Krohn-Rhodes theorem provides the framework for proving our preservation results, and our techniques are based on ergodic theory of shift spaces.

Dominique PERRIN (Paris, France)

Title: A survey on substitution shifts

Abstract: In this talk, I will present the main results contained in our book 'Substitutions and Symbolic Dynamics' written with Marie-Pierre Béal and Fabien Durand (Cambridge University Press, to appear end of 2026). I will cover the main results concerning recognizability, derivatives of morphic shifts, complexity, etc. Many examples will be provided. I will also mention at the end some important open problems.

Svetlana PUZYNINA (St. Petersburg, Russia)

Title: On group complexity of infinite words

Abstract: A classical notion of a factor complexity of an infinite word is defined as a function p(n) counting, for each n, the number of distinct factors (or blocks of consecutive letters) of the word of length n. The notion has various generalizations and variants. For example, the abelian complexity p_{ab}(n) counts the number of distinct factors of each length n up to abelian equivalence, i.e., only the numbers of occurrences of each letter is taken into account, and not their order. The notion of a group complexity generalizes both notions of a factor and an abelian complexities. Namely, given a sequence \omega=(G_n)_{n=1}^{\infty} of subgroups of the symmetric group S_n, group complexity p_{\omega}(n) of a word counts the number of classes of factors of each length n of the word, where words obtained from one another by permutations from G_n are put in the same class. Taking G_n=S_n, we obtain the abelian complexity, and taking G_n=Id, we recover the factor complexity. Clearly, group complexity value is between the abelian and the factor complexities. In this talk, we will discuss this notion of complexity, its possible values and relations with periodicity and the family of Sturmian words.

Giuseppe ROMANA (Palermo, Italy)

Title: When does a measure become a “repetitiveness measure”?

Abstract: Over the last decade, various repetitiveness measures of words have emerged as central notions in data compression and compressed text indexing, due to the growing need to store and query highly redundant data. Yet, as different approaches exploit repetitions in the text in different ways, a formal definition of measure of repetitiveness is missing; instead, the “repetitiveness” label is usually attached to a measure when certain problems in combinatorial pattern matching can be solved in a space proportional to the measure itself.

In this talk, we attempt to unveil the properties that make a measure a repetitiveness measure, and provide an overview of the mutual relationship among these measures. Moreover, we will go through different problems concerning the “sensitivity” of such measures when simple combinatorial operations are applied to words.

Accepted contributions

Mélodie Andrieu and Léo Vivion, Beyond Rauzy's conjecture on abelian complexity
Marcella Anselmo, Dora Giammarresi, Maria Madonia and Carla Selmi, Extending Fibonacci words to two dimensions
Olivier Bodini and Francis Durand, Entropic Exact Size Tree Sampling via a Continuous Relaxation of the Degree Profile Distribution
Srecko Brlek, Remarks on Pattern complexities
Giuseppa Castiglione, Sabrina Mantaci, Giuseppe Romana, Antonio Restivo and Marinella Sciortino, Discriminative Absent Words: Recent Developments and Perspectives
Francesco Dolce and Christian Hughes, Some Results on Fixed Points of the Burrows-Wheeler Transform
Ľubomíra Dvořáková and Edita Pelantová, Reflection on the reflection complexity
Ľubomíra Dvořáková and Martina Moravcová, Critical exponent of simple Parry sequences
Sébastien Ferenczi and Luca Q. Zamboni, Clustering, order conditions, and return words of interval exchanges
Raphaël Henry and Julien Cassaigne, The complexity of smooth words over binary alphabets
Gandhar Joshi, Greedy equivalences of certain Dumont–Thomas numeration systems
Shuo Li and Yuan Song, More Pattern-Counting Results Using Graph-Theoretic Methods
Zuzana Masákova, J. Mazáč and Edita Pelantová, Linear Self-Similarities of Cut-and-Project Sets: Characterization and Construction
Antoine Renard, A stroll around binomial coefficients
Aleksi Vanhatalo, On finite test sets of square-freeness of h(L)