Differences

This shows you the differences between two versions of the page.

--- 2023 [2024/01/24 08:12] – created 139.124.146.3
+++ 2023 [2024/01/24 08:15] (current) – 139.124.146.3
@@ Line 1: / Line 1: @@
-One world
+Here are the talks of [[https://www.i2m.univ-amu.fr/wiki/Combinatorics-on-Words-seminar/start|One World Combinatorics on Words Seminar]] dated 2023.
+==== Past talks 2023 ====
+**December 19 2023: [[https://www.pierrebeaur.fr/|Pierre Béaur]]** //All I want for Christmas is an algorithm to detect a Sturmian word in an ω-regular language//
+{{ seminar2023:20231219beaur.pdf |slides}}
+{{ seminar2023:20231219beaur.mp4 |video of the talk}}
+In the enchanting realm of CoWLand, where computer science wizards and mathematics enchanters gather via the magic of the Internet, a whimsical elf embarks us on a yuletide adventure. Our quest? To detect Sturmian words hidden in the snowy languages of ω-regular automata. As S-adic representations and discrete lines dance around the Christmas tree, I will present the mischevious magic of desubstitution and its algorithmic applications.
+I start from weak ω-automata, that is, labeled graphs that accept infinite words, and characterize when such automata accept a substitutive word, a  fixed point, or a Sturmian word. These methods are effective and provide an algorithm relying on S-adic representations. On the way, we find some other natural applications in combinatorics on words and discrete geometry. Then, I will explain how the methods translate from weak ω-automata to Büchi automata, what the limits of our techniques are, and what are the leads to give this fairytale a proper conclusion.
+**December 5 2023: [[https://www.lirmm.fr/~mrosenfeld/|Matthieu Rosenfeld]]** //Word reconstruction using queries on subwords or factors//
+{{ seminar2023:20231205rosenfeld.pdf |slides}}
+{{ seminar2023:20231205rosenfeld.mp4 |video of the talk}}
+I will present some results that we recently obtained about word
+reconstruction problems. In this setting you can ask queries from a
+fixed family of queries about an unknown word $W$ and your goal is to
+reconstruct $W$ by asking the least possible number of queries. We study
+the question for 3 different families of queries:
+- "How many occurrences of $u$ in $W$ as a factor?", for any $u$;
+- "How many occurrences of $u$ in $W$ as a subword?", for any $u$;
+- "Does $u$ occur in $W$ as a subword?", for any $u$.
+Each of these cases had already been studied, and we improve the
+bounds for each of them.
+In particular, in the second case, you can ask queries about the
+number of occurrences of any given subword. Fleischmann, Lejeune,
+Manea, Nowotka and Rigo gave an algorithm that reconstructs any
+binary word $W$ of length $n$ in at most $n/2 +1$ queries. We prove that
+$O((n log n)^{(1/2)})$ queries suffice. In this talk, I will provide a few
+necessary definitions and present our results.
+This is joint work with Gwenaël Richomme.
+**November 21 2023: [[https://www.researchgate.net/profile/Seda-Albayrak-3|Seda Albayrak]]** //Quantitative estimates for the size of an intersection of
+sparse automatic sets//
+{{ seminar2023:20231121albayrak.pdf |slides}}
+{{ seminar2023:20231121albayrak.mp4 |video of the talk}}
+In 1979, Erdős conjectured that for $k \ge 9$, $2^k$ is
+not the sum of distinct powers of $3$. That is, the set of powers of
+two (which is $2$-automatic) and the $3$-automatic set consisting of
+numbers whose ternary expansions omit $2$ has finite intersection. A
+theorem of Cobham (1969) says that if $k$ and $\ell$ are two
+multiplicatively independent natural numbers then a subset of the
+natural numbers that is both $k$- and $\ell$-automatic is eventually
+periodic.  A multidimensional extension of this theorem was later
+given by Semenov (1977).  Motivated by Erdős’ conjecture and in
+light of Cobham’s theorem, we give a quantitative version of the
+Cobham-Semenov theorem for sparse automatic sets, showing that the
+intersection of a sparse $k$-automatic subset of $\mathbb{N}^d$ and a
+sparse $\ell$-automatic subset of $\mathbb{N}^d$ is finite. Moreover,
+we give effectively computable upper bounds on the size of the
+intersection in terms of data from the automata that accept these
+sets.
+**November 7 2023: [[https://users.math-cs.spbu.ru/~puzynina/|Svetlana Puzynina]]** //Well distributed occurrences property in infinite words//
+{{ seminar2023:20231107-puzynina.pdf |slides}}
+{{ seminar2023:20231107-puzynina.mp4 |video of the talk}}
+We say that an infinite word $u$ on a $d$-ary alphabet has the well distributed occurrences  property if, for each factor $w$ of $u$, each positive integer $m$, and each vector $v\in {\mathbb Z}_m^d$, there is an occurrence of $w$ such that the Parikh vector of the prefix of $u$ preceding such occurrence is congruent to $v$ modulo $m$. In this talk we will discuss how aperiodic infinite words with well distributed occurrences can be used to produce aperiodic pseudorandom number generators with good statistical behavior. We study the well distributed occurrences property for certain families of  infinite words including words generated by morphisms, Sturmian words and Arnoux–Rauzy words. The talk is based on new and old results.
+**October 24 2023: [[https://www.researchgate.net/scientific-contributions/Herman-Goulet-Ouellet-2195681482|Herman Goulet-Ouellet]]** //Density of rational languages under invariant measures//
+{{ seminar2023:20231024goulet-ouellet.pdf |slides}}
+{{ seminar2023:20231024goulet-ouellet.mp4 |video of the talk}}
+The notion of density for languages was studied by Schützenberger in the 60s and by Hansel and Perrin in the 80s. In both cases, the authors focused on densities defined by Bernoulli measures. In this talk, I will present new results about densities of regular languages under invariant measures of minimal shift spaces. We introduce a compatibility condition which implies convergence of the density to a constant which depends only on the given rational language. This result can be seen as a form of equidistribution property. The compatibility condition can be stated either in terms of return words or of a skew product. The passage between the two forms is made more transparent using simple combinatorial tools inspired by ergodic theory and cohomology. This is joint work with Valérie Berthé, Carl-Fredrik Nyberg Brodda, Dominique Perrin and Karl Petersen.
+**October 10 2023: [[https://kmlinux.fjfi.cvut.cz/~balkolub/|Ľubomíra Dvořáková]]** //String attractors and pseudopalindromic closures//
+{{ seminar2023:20231010dvorakova.pdf |slides}}
+{{ seminar2023:20231010dvorakova.mp4 |video of the talk}}
+In this contribution we carry on a study of string attractors of important classes of sequences.
+Attractors of minimum size of factors/prefixes/particular prefixes of the following sequences have been determined so far: Sturmian sequences (Mantaci, Restivo, Romana, Rosone, Sciortino, 2021, Dvořáková, 2022), episturmian sequences (Dvořáková, 2022), the Tribonacci sequence (Schaeffer and Shallit, 2021), the Thue-Morse sequence (Kutsukake, 2020, Schaeffer and Shallit, 2021, Dolce, 2023), the period-doubling sequence (Schaeffer and Shallit, 2021), the powers of two sequence (Schaeffer and Shallit, 2021, Kociumaka, Navarro, Prezza, 2021), complementary-symmetric Rote sequences (Dvořáková and Hendrychová, 2023).
+Recently, string attractors in fixed points of k-bonacci-like morphisms have been described (Gheeraert, Romana, Stipulanti, 2023).
+In our talk we aim to present the following results:
+Using the fact that standard Sturmian sequences may be obtained when iterating palindromic closure, we were able to find attractors of minimum size of all factors of Sturmian sequences. These attractors were different from the ones found for prefixes by Mantaci et al. It was then straightforward to generalize the result to factors of episturmian sequences.
+Observing usefullness of palindromic closures when dealing with attractors, we turned our attention to pseudopalindromic prefixes of the so-called binary generalized pseudostandard sequences. We determined the minimum size attractors in two cases: for pseudostandard sequences obtained when iterating uniquely the antipalindromic closure (the minimum size is three) and for the complementary-symmetric Rote sequences when iterating both palindromic and antipalindromic closure (the minimum size is two).
+**September 26 2023:[[https://www.uwinnipeg.ca/mathstats/faculty/james-currie.html}|James Currie]]** //The analogs of overlap-freeness for the period-doubling morphism and
+for the Fibonacci morphism//
+{{ seminar2023:20230926currie.pdf |slides}}
+{{ seminar2023:20230926currie.mp4 |video of the talk}}
+The Thue-Morse morphism is the binary map $\mu: 0 \to 01, 1 \to 10$. A word $w$ is
+overlap-free if it has no factor of the form $xyxyx$, where $x$ is
+non-empty. A deep connection between these two concepts is the engine
+behind several results:
+-         The precise characterization of finite prefixes of infinite
+overlap-free binary words (Fife’s Theorem);
+-         A precise enumeration of overlap-free binary words;
+-         A characterization of all binary patterns encountered by the
+Thue-Morse word;
+-         The determination of the lexicographically least infinite
+overlap-free word.
+Given another morphism, is there an analog of overlap-freeness which
+facilitates the proof of similar results? We show that the answer is
+yes for the period doubling morphism $\delta :0 \to 01, 1\to 00$, and for the
+Fibonacci morphism $\varphi :0\to 01, 1\to 0$.
+** September 12 2023:**  **[[https://www.researchgate.net/scientific-contributions/Bastian-Espinoza-2179194104|Bastián Espinoza]]** //An $S$-adic characterization of linear-growth complexity subshifts//
+{{ seminar2023:20230912espinoza.pdf |slides}}
+{{ seminar2023:20230912espinoza.mp4 |video of the talk}}
+In the context of symbolic dynamics, the class of "linear-growth complexity subshifts" is of particular relevance as it occurs in a variety of areas, such as geometric dynamical systems, language theory, number theory, and numeration systems, among others. During the intensive study carried out on this subject since the beginning of the 90s, it was proposed that a hierarchical decomposition based on $S$-adic sequences that characterizes linear-growth complexity subshifts would be useful to understand this class. The problem of finding such a characterization was given the name "$S$-adic conjecture" and inspired several influential results in symbolic dynamics. In this talk, I will present an $S$-adic characterization of this class as well as some of its applications, giving in particular a solution to this conjecture.
+**May 15 2023: [[https://cs.uwaterloo.ca/~csk/|Craig Kaplan]]** //An aperiodic monotile//
+{{ seminar2023:20230515kaplan.pdf |slides}}
+{{ seminar2023:20230515kaplan.mp4 |video of the talk}}
+A set of shapes is called aperiodic if the shapes admit tilings of
+ the plane, but none that have translational symmetry.  A longstanding
+ open problem asks whether a set consisting of a single shape could
+ be aperiodic; such a shape is known as an aperiodic monotile or
+ sometimes an "einstein".  The recently discovered "hat" monotile
+ settles this problem in two dimensions.  In this talk I provide
+ necessary background on aperiodicity and related topics in tiling
+ theory, review the history of the search for for an aperiodic
+ monotile, and then discuss the hat and its mathematical properties.
+Full disclosure: this is the same title and abstract that I just sent to Kevin Hare for the Numeration seminar the week before (May 9th).  I expect that the talks will be largely the same, but if I have a chance to incorporate any connections to combinatorics on words into my talk for you, I will.
+**May 8 2023: [[https://lapointemelodie.github.io/publications/|Mélodie Lapointe]]** //Perfectly clustering words: Induction and morphisms//
+{{ seminar2023:20230508lapointe.pdf |slides}}
+{{ seminar2023:20230508lapointe.mp4 |video of the talk}}
+Perfectly clustering words are special factors in trajectories of discrete interval exchange transformation with symmetric permutation. If the discrete interval exchange transformation has two intervals, they are Christoffel words. Therefore, perfectly clustering words are a natural generalization of Christoffel words. In this talk, an induction on discrete interval exchange transformation with symmetric permutation will be presented. This induction sends a discrete interval exchange transformation with symmetric permutation into another one with the same permutation but smaller intervals. Moreover, the induction leads to morphisms, sending a perfectly clustering word to another perfectly clustering word. Finally, a new bijection between perfectly clustering words and band bricks over certain gentle algebras will be presented.
+** April 3 2023: [[https://cs.uwaterloo.ca/~shallit/|Jeffrey O. Shallit]]** //New Results in Additive Number Theory via Combinatorics on Words//
+{{ seminar2023:20230403shallit.pdf |slides}}
+{{ seminar2023:20230403shallit.mp4 |video of the talk}}
+Additive number theory is the study of the additive properties of integers.
+Surprisingly, we can use techniques from combinatorics on words to prove
+results in this area.
+In this talk I will discuss the number of representations of an integer N as
+a sum of elements from some famous sets, such as the evil numbers, the
+odious
+numbers, the Rudin-Shapiro numbers, Wythoff sequences, etc.
+** Mar 27 2023: [[https://fit.cvut.cz/cs/fakulta/lide/5367-stepan-starosta|Štěpán Starosta]]** //On a faithful representation of Sturmian morphisms//
+{{ seminar2023:20230327starosta.pdf |slides}}
+{{ seminar2023:20230327starosta.mp4 |video of the talk}}
+The set of morphisms mapping any Sturmian sequence to a Sturmian sequence forms together with composition the so-called monoid of Sturm.  For this monoid, we define a faithful representation by $(3\times 3)$-matrices with integer entries. We find three convex cones in $\mathbb{R}^3$ and show that a matrix $R \in  Sl(\mathbb{Z},3)$ is a matrix representing a Sturmian morphism if the three cones are  invariant under multiplication by $R$ or $R^{-1}$. This property offers a new tool to study Sturmian sequences. We provide
+alternative proofs of four known results on Sturmian sequences fixed by a primitive morphism and a new result concerning the square root of a Sturmian sequence.
+** Mar 6 2023: Léo Poirier and [[https://www.irif.fr/~steiner/|Wolfgang Steiner]]** //Factor-balanced $S$-adic languages//
+{{ seminar2023:20230306poirier_steiner.pdf |slides}}
+{{ 20230306poirier_steiner.mp4 |video of the talk}}
+A set of words, also called a language, is letter-balanced if the number of occurrences of each letter only depends on the length of the word, up to a constant. Similarly, a language is factor-balanced if the difference of the number of occurrences of any given factor in words of the same length is bounded. The most prominent example of a letter-balanced but not factor-balanced language is given by the Thue-Morse sequence. We establish connections between the two notions, in particular for languages given by substitutions and, more generally, by sequences of substitutions. We show that the two notions essentially coincide when the sequence of substitutions is proper. For the example of Thue-Morse-Sturmian languages, we give a full characterisation of factor-balancedness.
+** Feb 27 2023: [[https://perso.liris.cnrs.fr/aline.parreau/|Aline Parreau]]** and **[[https://perso.liris.cnrs.fr/eric.duchene/|Eric Duchêne]]** //Taking and merging games as rewrite games // (joint work with V. Marsault and M. Rigo)
+{{ seminar2023:20230227duchene-parreau.pdf |slides}}
+{{ seminar2023:20230227duchene-parreau.mp4 |video of the talk}}
+In this talk, we present some of the links between combinatorial games and language theory. A combinatorial game is a 2-player game with no chance and with perfect information. Amongst them, the family of heap games such as the game of Nim, subtraction or octal games belong to the the most studied ones. Generally, the analysis of such games consist in determining which player has a winning strategy. We will first see how this question is investigated in the case of heap games.
+In a second part of the talk, we will present a generalization of heap games as rewrite games on words. This model was introduced by Waldmann in 2002. Given a finite alphabet and a set of rewriting rules on it, starting from a finite word w, each player alternately applies a rule on w. The first player unable to apply a rule loses the game. In this context, the main question is now about the class of the language formed by the losing and winning positions of the game. For example, for octal games that are solved in polynomial time, the losing positions form a rational language. By using the model of rewrite games, we will investigate here a new family of heap games that consist in merging heaps of tokens, and consider some of the different classes of languages that may emerge according to the rules of the game.
+** Feb 6 2023: Matthew Konefal** //Examining the Class of Formal Languages which are Expressible via Word Equations//
+{{ seminar2023:20230206konefal.pdf |slides}}
+{{ seminar2023:20230206konefal.mp4 |video of the talk}}
+A word equation can be said to express a formal language via each variable occurring in it. The class $WE$ of formal languages which can be expressed in this way is not well understood. I will discuss  a number of necessary and sufficient conditions for a formal language $L$ to belong to $WE$. I will give particular focus to the case in which $L$ is regular, and to the case in which $L$ is a submonoid.
+** Jan 23 2023: [[https://kmlinux.fjfi.cvut.cz/~balkolub/|Lubomíra Dvořáková]]** //Essential difference between the repetitive thereshold and asymptotic repetitive threshold of balanced sequences//
+{{ seminar2023:20230123dvorakova.pdf |slides}}
+{{ seminar2023:20230123dvorakova.mp4 |video of the talk}}
+At first, we will summarize both the history and the state of the art of the critical exponent and the asymptotic critical exponent of balanced sequences.
+Second, we will colour the Fibonacci sequence by suitable constant gap sequences to provide an upper bound on the asymptotic repetitive threshold of $d$-ary balanced sequences. The bound is attained for $d$ equal to $2$, $4$ and $8$ and we conjecture that it happens for infinitely many  even $d$'s.
+Finally, we will reveal an essential difference in behavior of the repetitive threshold and  the asymptotic repetitive threshold of balanced sequences: The repetitive threshold of $d$-ary  balanced sequences is known to be  at least $1+1/(d-2)$ for each $d$ larger than two. In contrast, our bound implies that the asymptotic repetitive threshold of $d$-ary balanced sequences is at most $1+\phi^3/2^{d-3}$ for each $d$ larger than one, where $\phi$ is the golden mean.
+Joint work with Edita Pelantová.
+** Jan 9: [[https://www.tompeteder.org/|Pamela Fleischmann]]** //$m$-Nearly $k$-Universal Words - Investigating Simon Congruence//
+Determining the index of the Simon congruence is a long outstanding open problem. Two words $u$ and $v$ are called Simon congruent if they have the same set of scattered factors, which are parts of the word in the correct order but not necessarily consecutive, e.g., oath is a scattered factor of logarithm. Following the idea of scattered factor $k$-universality, we investigate $m$-nearly $k$-universality, i.e., words where $m$ scattered factors of length $k$ are absent, w.r.t. Simon congruence. We present a full characterisation as well as the index of the congruence for $m = 1$, $2$, and $3$. Moreover, we present a characterisation of the universality of repetitions.
+{{ seminar2023:20230109fleischmann.pdf |slides}}
+{{ seminar2023:20230109fleischmann.mp4 |video of the talk}}