XX

Journées montoises
d'informatique théorique

Naples, Italie, 7-10 sep. 2026

La conférence

La 20e édition des Journées Montoises d'Informatique Théorique se tiendra à l'Université Federico II de Naples du 7 (après-midi) au 10 (matin) septembre 2026. Comme lors des éditions précédentes, ces journées comprendront des exposés invités et des exposés sélectionnés sur la base de résumés.

Les thèmes principaux de la conférence sont la combinatoire et les algorithmes sur les mots, la théorie des automates et des langages formels, les systèmes dynamiques discrets et la dynamique symbolique, la logique et les méthodes formelles.

Elle accueille également d'autres branches de l'informatique théorique et des mathématiques discrètes liées à ces domaines (théorie des nombres, calculabilité, semi-groupes, pavages, théorie des jeux, géométrie discrète, bio-informatique, etc.).

Les langues officielles de la conférence sont l'anglais et le français.

Lieu

Università degli Studi di Napoli Federico II

Scuola Politecnica e delle Scienze di Base

Piazzale Tecchio, 80

Naples, Italie

Google Maps

Inscription

Des frais d'inscription sont exigés pour participer, comme indiqué ci-dessous. Au moins une inscription est requise par résumé accepté.

Pour bénéficier du tarif étudiant, il est nécessaire d'être inscrit en licence, master ou doctorat au moment de l'inscription.

Les frais comprennent au minimum le matériel de la conférence, toutes les pauses-café et le banquet. Ils doivent être réglés par virement bancaire, en suivant les instructions ci-dessous ; veuillez noter qu’après le 28 août, seule l’inscription sur place en espèces à l’arrivée sera possible.

Pour finaliser l'inscription, il est nécessaire d'envoyer un e-mail à jm26@easychair.org en joignant la preuve du virement bancaire et en précisant les informations suivantes : nom complet, affiliation, titre de la présentation (le cas échéant), dates d'arrivée et de départ (si connues), ainsi que toute restriction alimentaire ou exigence particulière.

Dates importantes

Soumission des résumés (étendue) : 29 mai 10 juin 2026, AoE

Notification d'acceptation : 3 juillet 2026

Date limite d'inscription avant majoration : 17 juillet 2026

Début de la conférence : 7 septembre 2026 (après-midi)

Fin de la conférence : 10 septembre 2026 (matin)

Exposés invités

Pamela FLEISCHMANN (Kiel, Allemagne)

Titre : Scattered Factor Universality - A Survey

Résumé : 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 (Sarrebruck, Allemagne)
Titre : Preservation theorems for transducer outputs

Résumé : 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)

Titre : A survey on substitution shifts

Résumé : 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 (Saint-Pétersbourg, Russie)

Titre : On group complexity of infinite words

Résumé : 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 (Palerme, Italie)

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

Résumé : 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.

Résumés acceptés

Mélodie Andrieu et Léo Vivion, Beyond Rauzy's conjecture on abelian complexity
Marcella Anselmo, Dora Giammarresi, Maria Madonia et Carla Selmi, Extending Fibonacci words to two dimensions
Olivier Bodini et 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 et Marinella Sciortino, Discriminative Absent Words: Recent Developments and Perspectives
Francesco Dolce et Christian Hughes, Some Results on Fixed Points of the Burrows-Wheeler Transform
Ľubomíra Dvořáková et Edita Pelantová, Reflection on the reflection complexity
Ľubomíra Dvořáková et Martina Moravcová, Critical exponent of simple Parry sequences
Sébastien Ferenczi et Luca Q. Zamboni, Clustering, order conditions, and return words of interval exchanges
Raphaël Henry et Julien Cassaigne, The complexity of smooth words over binary alphabets
Gandhar Joshi, Greedy equivalences of certain Dumont–Thomas numeration systems
Shuo Li et Yuan Song, More Pattern-Counting Results Using Graph-Theoretic Methods
Zuzana Masákova, J. Mazáč et 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)