BEGIN:VCALENDAR VERSION:2.0 PRODID:-//cow-seminar.github.io//seminar//EN X-WR-CALNAME:One World Combinatorics on Words Seminar CALSCALE:GREGORIAN BEGIN:VEVENT UID:20200629-mol@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20200629T130000Z DTEND:20200629T140000Z SUMMARY:Lucas Mol: Extremal Square-Free Words and Variations DESCRIPTION:(joint work with Narad Rampersad and Jeffrey Shallit)\n\nA squa re-free word $w$ over a fixed alphabet $\\Sigma$ is *extremal* if every wo rd obtained from $w$ by inserting a single letter from $\\Sigma$ (at any p osition) contains a square. Grytczuk et al. recently introduced the concep t of extremal square-free word\, and demonstrated that there are arbitrari ly long extremal square-free words over a ternary alphabet. One can define extremal overlap-free words\, and more generally\, extremal $\\beta$-free words\, analogously. We characterize the lengths of extremal square-free ternary words\, and the lengths of extremal overlap-free binary words. We also establish that there are arbitrarily long extremal $\\beta$-free bina ry words for every $2 < \\beta \\leq 8/3$. We include a variety of interes ting conjectures and open questions. URL:https://cow-seminar.github.io/archives/2020.html#20200629-mol END:VEVENT BEGIN:VEVENT UID:20200713-rigo@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20200713T130000Z DTEND:20200713T140000Z SUMMARY:Michel Rigo: Binomial$^3$ : coefficients\, equivalence\, complexity ... DESCRIPTION:The binomial coefficient $x \\choose y$ of the words $x$ and $y $ is the number of times $y$ appears as a (scattered) subword of $x$. This concept has received a lot of attention\, e.g.\, Simon's congruence\, Par ikh matrices\, reconstruction problem\, ... A few years ago\, we introduce d the $k$-binomial equivalence: Two words $u$ and $v$ are $k$-binomially e quivalent if the binomial coefficients $u \\choose x$ and $v \\choose x$ a gree for all words $x$ of length up to $k$. This is a refinement of the us ual abelian equivalence.\n\nFirst\, I will review several results (joint w ork with P. Salimov\, M. Lejeune\, J. Leroy\, M. Rosenfeld) related to $k$ -binomial complexity (where factors of length $n$ are counted up to $k$-bi nomial equivalence) for Sturmian words\, Thue-Morse word and Tribonacci wo rd. Then I will concentrate on $k$-binomial equivalence classes for finite words. In particular\, I will discuss the fact that the submonoid generat ed by the generators of the free nil-$2$ group on $m$ generators is isomor phic to the quotient of the free monoid $\\{1\,...\,m\\}^∗$ by the $2$-b inomial equivalence (joint work with M. Lejeune\, M. Rosenfeld). URL:https://cow-seminar.github.io/archives/2020.html#20200713-rigo END:VEVENT BEGIN:VEVENT UID:20200720-vuillon@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20200720T130000Z DTEND:20200720T140000Z SUMMARY:Laurent Vuillon: Combinatorics on words for Markoff numbers DESCRIPTION:(joint work with Christophe Reutenauer) [paper](https://math.bo ku.ac.at/udt/vol12/no2/03ReutVuill.pdf)\n\nMarkoff numbers are fascinating integers related to number\ntheory\, Diophantine equation\, hyperbolic ge ometry\, continued fractions\nand Christoffel words. Many great mathematic ians have worked on these\nnumbers and the $100$ years famous uniqueness c onjecture by Frobenius is\nstill unsolved. In this talk\, we state a new f ormula to compute the\nMarkoff numbers using iterated palindromic closure and the Thue-Morse\nsubstitution. The main theorem shows that for each Mar koff number $m$\,\nthere exists a word $v\\in \\{a\,b\\}^*$ such that $m −2$ is equal to the length of the iterated palindromic\nclosure of the i terated antipalindromic closure of the word $av$. This\nconstruction gives a new recursive construction of the Markoff numbers\nby the lengths of th e words involved in the palindromic closure. URL:https://cow-seminar.github.io/archives/2020.html#20200720-vuillon END:VEVENT BEGIN:VEVENT UID:20200727-currie@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20200727T130000Z DTEND:20200727T140000Z SUMMARY:James Currie: Remarks on Pansiot encodings DESCRIPTION:Pansiot encodings were an essential ingredient in the solution of Dejean's conjecture. We discuss these encodings\, and the related group theoretic notions\, in a way perhaps more natural to combinatorics on wor ds\, namely\, in terms of De Bruijn graphs. We discuss variations on Pansi ot encodings\, with applications to circular words\, and to the undirected threshold problem. URL:https://cow-seminar.github.io/archives/2020.html#20200727-currie END:VEVENT BEGIN:VEVENT UID:20200914-yassawi@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20200914T130000Z DTEND:20200914T140000Z SUMMARY:Reem Yassawi: The Ellis semigroup of bijective substitution shifts DESCRIPTION:Joint work with Johannes Kellendonk.\n\nGiven a substitution $\ \theta : \\mathcal A \\to \\mathcal A^\\ell$ of length $\\ell$ on a finite alphabet $\\mathcal A$\, the substitution shift $(X_\\theta\, \\sigma)$ i s the topological dynamical system where $X_\\theta$ consists of bi-infini te sequences all of whose subwords belong to $\\theta$'s language\, and $\ \sigma$ is the left shift map\, which defines a $\\mathbb Z$-action on $X_ \\theta$. As for any topological dynamical system we can study the Ellis s emigroup $E(X_\\theta\, \\sigma)$ of $(X_\\theta\, \\sigma)$ (also called the enveloping semigroup). Elements of $E(X_\\theta\, \\sigma)$ are functi ons on $X_\\theta$ which are pointwise limits of some net $(\\sigma^{n_k}) $. In other words\, $E(X_\\theta\, \\sigma)$ is the compactification of th e group action generated by $\\sigma$ in the topology of pointwise converg ence on the space $X_\\theta^{X_\\theta}$. The Ellis semigroup is typicall y a huge beast\, and its computation has been restricted mainly to systems $(X\, \\sigma)$ which are metrically group rotations that are tame\, mean ing that the Ellis semigroup has cardinality at most that of the continuum .\n\nIn this talk we give an explicit algebraic description of the Ellis s emigroup for the family of bijective substitution shifts. These systems ar e not tame. Along the way we classify the idempotents\, left and right ide als\, and the kernel of $E(X_\\theta\, \\sigma)$. We also discover a notio n of generalised height of a substitution\, which generalises the classica l notion defined by Kamae and Dekking. URL:https://cow-seminar.github.io/archives/2020.html#20200914-yassawi END:VEVENT BEGIN:VEVENT UID:20200928-peltomaki@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20200928T130000Z DTEND:20200928T140000Z SUMMARY:Jarkko Peltomäki: Avoiding abelian powers cyclically DESCRIPTION:A finite word $w$ avoids abelian $N$-powers cyclically if for e ach\nabelian $N$-power of period $m$\, we have $m \\geq |w|$. This notion\ ngeneralizes circular avoidance of $N$-powers in two ways. Firstly\n"power " is replaced by "abelian power" and secondly circular avoidance\nconcerns only the conjugacy class of a word\, but here we require even\nmore. Let $\\mathcal{A}(k)$ be the least integer $N$ such that for all\n$n$ there ex ists a word of length $n$ over a $k$-letter alphabet that\navoids abelian $N$-powers cyclically. Let $\\mathcal{A}_\\infty(k)$ be the\nleast integer $N$ such that there exist arbitrarily long words over a\n$k$-letter alpha bet that avoid abelian $N$-powers cyclically.\n\nI will sketch the proofs of the following results: 1) $5 \\leq\n\\mathcal{A}(2) \\leq 8$\, $3 \\leq \\mathcal{A}(3) \\leq 4$\, $2 \\leq\n\\mathcal{A}(4) \\leq 3$\, $\\mathca l{A}(k) = 2$ for $k \\geq 5$\; 2)\n$\\mathcal{A}_\\infty(2) = 4$\, $\\math cal{A}_\\infty(3) = 3$\, and\n$\\mathcal{A}_\\infty(4) = 2$. If time permi ts\, I will discuss an\napplication to the growth rates of exponents of ab elian powers occurring\nin infinite binary words. URL:https://cow-seminar.github.io/archives/2020.html#20200928-peltomaki END:VEVENT BEGIN:VEVENT UID:20201005-grytczuk@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20201005T130000Z DTEND:20201005T140000Z SUMMARY:Jarosław Grytczuk: Graph Coloring and Combinatorics on Words DESCRIPTION:I will present a few problems inspired mutually by various issu es studied in the two disciplines of the title. For instance\, given any s equence of 3-letter alphabets\, is it possible to pick a letter from each alphabet so that the resulting word is *square-free*? The case of equal al phabets is covered by the famous result of Thue\, but intuition tells us t hat this should be the hardest case (the more different letters in the pla y\, the easier to avoid repeated factors). While more than one has attacke d the problem\, the question remains unanswered\, which is especially frus trating as it has a positive answer with 4-letter alphabets.\nThe above qu estion was originally motivated by the *list coloring* problem\, a very po pular topic in graph coloring. However\, the opposite direction of inspira tion also leads to intriguing matters. For example\, how many letters are needed to label the vertices of a *planar graph* so that any word occurrin g along a simple path is square-free? It has been recently proved that 768 letters suffice\, but for a long time it was not known if any finite alph abet will do. Perhaps results of that type could be applied back to some p attern avoidability issues...? URL:https://cow-seminar.github.io/archives/2020.html#20201005-grytczuk END:VEVENT BEGIN:VEVENT UID:20201019-dekking@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20201019T130000Z DTEND:20201019T140000Z SUMMARY:Michel Dekking: The structure of Zeckendorf representations and bas e $\\varphi$ expansions DESCRIPTION:In the Zeckendorf numeration system natural numbers are represe nted as sums of Fibonacci numbers. In base $\\varphi$ natural numbers are represented as sums of powers of the golden mean $\\varphi$. Both represen tations have digits 0 and 1\, where the word 11 is not allowed. We know th at the Fibonacci numbers\, and the powers of $\\varphi$ are closely relate d\, as\, for example\, in the relation $\\varphi^n=F_{n-1}+F_n\\varphi$. I n fact\, Frougny and Sakarovitch have shown that Zeckendorf representation s can be transformed to base $\\varphi$ expansions by a 2-tape automaton. I will take a direct approach: what are the words that can occur in the Ze ckendorf representations\, and what are those that occur in base $\\varphi $ expansions? In which representations/expansions\, of which natural numb ers do they occur? URL:https://cow-seminar.github.io/archives/2020.html#20201019-dekking END:VEVENT BEGIN:VEVENT UID:20201026-rosenfeld@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20201026T140000Z DTEND:20201026T150000Z SUMMARY:Matthieu Rosenfeld: A simple proof technique to study avoidability of repetitions DESCRIPTION:I recently described a new proof technique that I used to study nonrepetitive colorings of graphs. This technique is in fact more general and seems to be as powerful as the Lovász local lemma or the entropy com pression method. For instance\, it has since been used by D.R. Wood and I .M. Wanless in the context of boolean satisfiability problem and of hyper graph colorings. In the particular context of combinatorics on words simil ar approaches had already been used by different authors\, but were never extended to graphs or other structures.\n\nIn this talk\, I will first pre sent some simple applications of the method to combinatorics on words and I will then explain how to extend this approach to nonrepetitive colorings of graphs of bounded degree. URL:https://cow-seminar.github.io/archives/2020.html#20201026-rosenfeld END:VEVENT BEGIN:VEVENT UID:20201109-rowland@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20201109T140000Z DTEND:20201109T150000Z SUMMARY:Eric Rowland: Avoiding fractional powers on an infinite alphabet DESCRIPTION:Questions concerning avoidability of patterns have been central to combinatorics on words since the work of Thue. In 2009\, Guay-Paquet a nd Shallit gave several results about pattern avoidance of words on the al phabet of natural numbers. Most patterns are avoidable on this alphabet\, but it is interesting to ask about the lexicographically least word that a voids a pattern. For fractional powers\, often this word is generated by a relatively simple morphism. In recent work with Manon Stipulanti\, we dis covered the structure of the lexicographically least $5/4$-power-free word on the natural numbers. In a surprising departure from previously studied words\, the morphism generating this word does not preserve $5/4$-power-f reeness. URL:https://cow-seminar.github.io/archives/2020.html#20201109-rowland END:VEVENT BEGIN:VEVENT UID:20201123-charlier@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20201123T140000Z DTEND:20201123T150000Z SUMMARY:Émilie Charlier: Regular sequences in abstract numeration systems DESCRIPTION:An abstract numeration system $S$ is given by a regular languag e $L$ over a totally ordered alphabet $(A\,<)$. The numeration language $L $ is ordered thanks to the radix (or genealogical) order induced by $<$. A natural number $n$ is then represented by the $n$-th word of the language (where we start counting from $n=0$). Integer bases $b$ and numeration sy stems based on a linear base sequence $U$ with a regular numeration langua ge are examples of abstract numeration systems. The notion of $b$-regular sequences was extended to abstract numeration systems by Maes and Rigo. Th eir definition is based on a notion of $S$-kernel that extends that of $b$ -kernel. However\, this definition does not allow us to generalize all of the many characterizations of $b$-regular sequences. In this talk\, I will present an alternative definition of $S$-kernel\, and hence an alternativ e definition of $S$-regular sequences\, that permits us to use recognizabl e formal series in order to generalize most (if not all) known characteriz ations of $b$-regular sequences. I will also show that an extra characteri zation can be obtained in the case of Pisot numeration systems. Finally\, I will consider the special cases of $S$-automatic and $S$-synchronized se quences. In particular\, we will see that the factor complexity of an $S$- automatic sequence defines an $S$-regular sequence. This is a joint work w ith Célia Cisternino and Manon Stipulanti. URL:https://cow-seminar.github.io/archives/2020.html#20201123-charlier END:VEVENT BEGIN:VEVENT UID:20201207-lejeune@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20201207T140000Z DTEND:20201207T150000Z SUMMARY:Marie Lejeune: Reconstructing words from right-bounded-block words DESCRIPTION:In this joint work with P. Fleischmann\, F. Manea\, D. Nowotka\ , and M. Rigo\, we study a variation of the famous reconstruction problem over words. It has been studied since $1973$. A survey of the different re sults will be held in the talk.\n\nWe study a variation of this problem.\n Let $\\mathcal{A}$ be a given alphabet and $n$ a natural number. We want t o reconstruct a hidden word $w \\in \\mathcal{A}^n$. To that aim\, we are allowed to pick a word $u_i$ and ask questions of the type "What is the mu ltiplicity of $u_i$ as subword of $w$?". Based on the answers to questions related to words $u_1\, \\ldots\, u_i$\, we can decide which will be the next question (i.e. decide which word will be $u_{i+1}$). We want to have the shortest sequence $(u_1\, \\ldots\, u_k)$ uniquely determining $w$.\n\ nWe naturally look for a value of $k$ less than the upper known bound for $k$-reconstructibility.\n\nWe will show how to reconstruct a binary word $ w$ from $m+1$ questions\, where $m$ is the minimum number of occurrences o f a and b in the word. We then reduce the problem for arbitrary finite al phabets to the binary case. We compare our bounds to the best known one fo r the classical reconstruction problem. URL:https://cow-seminar.github.io/archives/2020.html#20201207-lejeune END:VEVENT BEGIN:VEVENT UID:20201214-labbe@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20201214T140000Z DTEND:20201214T150000Z SUMMARY:Sébastien Labbé: A characterization of Sturmian sequences by indi stinguishable asymptotic pairs DESCRIPTION:We give a new characterization of Sturmian configurations in te rms of indistinguishable asymptotic pairs. Two asymptotic configurations o n a full $\\mathbb{Z}$-shift are indistinguishable if the sets of occurren ces of every pattern in each configuration coincide up to a finitely suppo rted permutation. This characterization can be seen as an extension to bii nfinite sequences of Pirillo's theorem which characterizes Christoffel wor ds. Furthermore\, we provide a full characterization of indistinguishable asymptotic pairs on arbitrary alphabets using substitutions and characteri stic Sturmian sequences. The proof is based on the well-known notion of de rived sequences.\n\nThis is joint work with Sebastián Barbieri and Štěp án Starosta. Preprint is available at https://arxiv.org/abs/2011.08112 URL:https://cow-seminar.github.io/archives/2020.html#20201214-labbe END:VEVENT BEGIN:VEVENT UID:20210104-frid@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210104T140000Z DTEND:20210104T150000Z SUMMARY:Anna Frid: Is not prefix palindromic length of a $k$-automatic word $k$-regular? DESCRIPTION:We consider the function of the prefix palindromic length for $ k$-automatic words and prove that it is $k$-regular for such words contain ing a finite number of distinct palindromes\, like for example the paperfo lding word. We also observe that in the opposite case\, if the number of d istinct palindromes is infinite\, this function can be $k$-regular\, as fo r the Thue-Morse word\, or seemingly not\, as for the period-doubling word . The fact of non-regularity\, however\, stays unproven.\n\nThis is a join t work with Enzo Laborde and Jarkko Peltomäki. The preprint is available at https://arxiv.org/abs/2009.02934. URL:https://cow-seminar.github.io/archives/2021.html#20210104-frid END:VEVENT BEGIN:VEVENT UID:20210201-allouche@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210201T140000Z DTEND:20210201T150000Z SUMMARY:Jean-Paul Allouche: Hidden automatic sequences DESCRIPTION:We discuss a joint work with Michel Dekking and Martine Queffé lec\n(https://arxiv.org/abs/2010.00920) about sequences given as\nfixed po ints of non-uniform morphisms that happen to be actually\nautomatic.\n\nOn e of the most ancien example is probably the one due to Berstel\,\nwho pro ved that the Istrail squarefree sequence defined as the fixed\npoint of th e morphism $f$ with $f(0) = 12$\, $f(1) = 102$\, $f(2) = 0$ is also\n$2$-a utomatic.\n\nAfter revisiting an old criterion due to M. Dekking at the en d of the 70's\,\nwe give several examples (in particular of sequences in t he OEIS).\nFinally we focus on morphisms associated with Grigorchuk(-like) groups. URL:https://cow-seminar.github.io/archives/2021.html#20210201-allouche END:VEVENT BEGIN:VEVENT UID:20210208-mercas@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210208T140000Z DTEND:20210208T150000Z SUMMARY:Robert Mercas: (Trying to do a) Counting of distinct repetitions in words DESCRIPTION:The\ntopic of counting the distinct repetitions that a word con tains has been around for at least two decades. The problem of counting di stinct squares in a word was introduced by Fraenkel and Simpson in ’98\, who also showed that their number is upper bounded by twice the length of the word. However\, their conjecture that the factor of 2 is superfluous (the length of the word is a strict bound) is still open (though there exi st several improvements of their original result). Moreover\, recently Man ea and Seki showed that proving the bound for binary words is enough. More over\, further work was done on counting distinct repetitions of higher ex ponent with quite sharp bounds.\nBy looking at non-extendable repetitions of power at least two (thus considering fractional ones as well) Kolpakov and Kucherov tried to bound in ‘99 the number of runs in a word (non-nec essarily distinct). This was recently shown to be less than the length $n$ of the word that we consider and more than 0.9482 times $n$.\nHowever\, a ll of these ideas have a common sticking point\, namely the three squares lemma of Crochemore and Rytter\, which they all use as main tool. In this talk I will present a different technique (which so far is not fully explo ited) of trying to count distinct squares and show some surprising connect ions between all of the above notions. URL:https://cow-seminar.github.io/archives/2021.html#20210208-mercas END:VEVENT BEGIN:VEVENT UID:20210215-ambroz@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210215T140000Z DTEND:20210215T150000Z SUMMARY:Petr Ambrož: Morphisms generating antipalindromic words DESCRIPTION:We introduce two classes of morphisms over the alphabet\n$A=\\{ 0\,1\\}$ whose fixed\npoints contain infinitely many antipalindromic facto rs. An\nantipalindrome is a finite word invariant\nunder the action of the antimorphism $E:\\{0\,1\\}^*\\to\\{0\,1\\}^*$\, defined\nby $E(w_1\\cdots w_n)=(1-w_n)\\cdots(1-w_1)$.\nWe conjecture that these two classes contai n all morphisms (up to\nconjugation) which generate infinite words with\ni nfinitely many antipalindromes. This is an analogue to the famous HKS\ncon jecture concerning infinite words\ncontaining infinitely many palindromes. We prove our conjecture for two\nspecial classes of morphisms\,\nnamely ( i) uniform morphisms and (ii) morphisms with fixed points\ncontaining also infinitely many palindromes. URL:https://cow-seminar.github.io/archives/2021.html#20210215-ambroz END:VEVENT BEGIN:VEVENT UID:20210222-reutenauer@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210222T140000Z DTEND:20210222T150000Z SUMMARY:Christophe Reutenauer: An arithmetical characterization of Christof fel words DESCRIPTION: URL:https://cow-seminar.github.io/archives/2021.html#20210222-reutenauer END:VEVENT BEGIN:VEVENT UID:20210222-cisternino@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210222T143000Z DTEND:20210222T153000Z SUMMARY:Célia Cisternino: Two applications of the composition of a $2$-tap e automaton and a weighted automaton DESCRIPTION: URL:https://cow-seminar.github.io/archives/2021.html#20210222-cisternino END:VEVENT BEGIN:VEVENT UID:20210222-dvorakova@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210222T150000Z DTEND:20210222T160000Z SUMMARY:Lubka Dvořáková: On balanced sequences with the minimal asymptot ic critical exponent DESCRIPTION: URL:https://cow-seminar.github.io/archives/2021.html#20210222-dvorakova END:VEVENT BEGIN:VEVENT UID:20210222-holub@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210222T153000Z DTEND:20210222T163000Z SUMMARY:Štěpán Holub: Formalization of Combinatorics on Words in Isabell e/HOL DESCRIPTION:We present an ongoing project of formalization of Combinatorics on Words\nin the proof assistant Isabelle/HOL. URL:https://cow-seminar.github.io/archives/2021.html#20210222-holub END:VEVENT BEGIN:VEVENT UID:20210222-manea@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210222T160000Z DTEND:20210222T170000Z SUMMARY:Florin Manea: Efficiently Testing Simon's Congruence DESCRIPTION:[full text](https://arxiv.org/abs/2005.01112)\n\nSimon's congru ence $\\sim_k$ is a relation on words defined by Imre Simon in the 1970s a nd intensely studied since then. This congruence was initially used in con nection to piecewise testable languages\, but also found many applications in\, e.g.\, learning theory\, databases theory\, or linguistics. The $\\s im_k$-relation is defined as follows: two words are $\\sim_k$-congruent if they have the same set of subsequences of length at most $k$. A long stan ding open problem\, stated already by Simon in his initial works on this t opic\, was to design an algorithm which computes\, given two words $s$ and $t$\, the largest $k$ for which $s\\sim_k t$. We propose the first algori thm solving this problem in linear time $O(|s|+|t|)$ when the input words are over the integer alphabet $\\{1\,\\ldots\,|s|+|t|\\}$ (or other alphab ets which can be sorted in linear time). Our approach can be extended to a n optimal algorithm in the case of general alphabets as well.\n\nTo achiev e these results\, we introduce a novel data-structure\, called Simon-Tree\ , which allows us to construct a natural representation of the equivalence classes induced by $\\sim_k$ on the set of suffixes of a word\, for all $ k\\geq 1$. We show that such a tree can be constructed for an input word i n linear time. Then\, when working with two words $s$ and $t$\, we compute their respective Simon-Trees and efficiently build a correspondence betwe en the nodes of these trees. This correspondence\, which can also be const ructed in linear time $O(|s|+|t|)$\, allows us to retrieve the largest $k$ for which $s\\sim_k t$. URL:https://cow-seminar.github.io/archives/2021.html#20210222-manea END:VEVENT BEGIN:VEVENT UID:20210222-andrieu@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210222T163000Z DTEND:20210222T173000Z SUMMARY:Mélodie Andrieu: A Rauzy fractal unbounded in all directions of th e plane DESCRIPTION:Until 2001 it was believed that\, as for Sturmian words\, the i mbalance of Arnoux-Rauzy words was bounded - or at least finite. Cassaign e\, Ferenczi and Zamboni disproved this conjecture by constructing an Arno ux-Rauzy word with infinite imbalance\, i.e. a word whose broken line devi ates regularly and further and further from its average direction.\nToday\ , we hardly know anything about the geometrical and topological properties of these unbalanced Rauzy fractals. The Oseledets theorem suggests that t hese fractals are contained in a strip of the plane: indeed\, if the Lyapu nov exponents of the matricial product associated with the word exist\, on e of these exponents at least is nonpositive since their sum equals zero.\ nThe study of the pairs of abelianized factors of Arnoux-Rauzy words dispr oves this belief. URL:https://cow-seminar.github.io/archives/2021.html#20210222-andrieu END:VEVENT BEGIN:VEVENT UID:20210301-postic@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210301T140000Z DTEND:20210301T150000Z SUMMARY:Mickaël Postic: Open and closed complexity functions of infinite w ords DESCRIPTION:Closed words\, also known as complete first returns\, have been studied for a long time\, and play an important role in symbolic dynamics . A word which is not closed is said to be open. In this talk based on a j oint work with Olga Parshina\, I will present a characterization of aperio dic words in terms of their open complexity function and closed complexity function\, in the spirit of Morse and Hedlund's theorem. The preprint is available at https://arxiv.org/pdf/2005.06254.pdf URL:https://cow-seminar.github.io/archives/2021.html#20210301-postic END:VEVENT BEGIN:VEVENT UID:20210315-stankiewicz@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210315T140000Z DTEND:20210315T150000Z SUMMARY:Szymon Stankiewicz: Square-free reducts of words DESCRIPTION:We discuss a joint work with Jarosław Grytczuk (https://arxiv. org/abs/2011.12822) about square-free reducts of words.\n\nIn any finite w ord one may delete the repeated block of a square\, obtaining thereby a sh orter word. By repeating this process\, a square-free word is eventually r eached\, which we call a reduct of the original word.\n\nWe will show that for each positive integer $n$ there is a word over ternary alphabet which can be reduced to at least $n$ different words and also that there is a w ord over alphabet of size four which has exactly $n$ reducts. We will also show that there exists infinitely many ternary words having exponential m any reducts in the length of these words.\n\nFor a fixed alphabet one can create a poset with nodes being words and $u > v$ iff word $u$ can be redu ced to word $v$. We will describe some properties of those posets. URL:https://cow-seminar.github.io/archives/2021.html#20210315-stankiewicz END:VEVENT BEGIN:VEVENT UID:20210322-palacio@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210322T140000Z DTEND:20210322T150000Z SUMMARY:Jane D. Palacio: Coverable bi-infinite substitution shifts DESCRIPTION:A finite or infinite word $w$ is said to be coverable if it can be formed by\noverlapping or adjacent occurrences of some finite subword $u$ of $w$. Coverability of finite words was introduced by A. Apostolico a nd A. Ehrenfeucht in the\ncontext of text algorithms in 1993. In 2004\, S. Marcus extended the concept\nof coverability to (one-sided) infinite sequ ences. In this presentation\, we will\ndefine the notion of coverable bi-i nfinite shifts.\n\nIn general\, coverability of subshifts is not topologic ally invariant. Nevertheless\, we show that a special type of coverability of substitutive shifts is invariant under topological conjugacy. To bette r understand coverability of\nbi-infinite shifts\, we aim to identify prop erties of substitutions that ensure\ncoverability or non-coverability of i ts associated shifts.\n\nThis is joint work with Manuel Joseph Loquias and Eden Delight Miro. URL:https://cow-seminar.github.io/archives/2021.html#20210322-palacio END:VEVENT BEGIN:VEVENT UID:20210322-aedo@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210322T143000Z DTEND:20210322T153000Z SUMMARY:Ibai Aedo: On long arithmetic progressions in binary Morse-like wor ds DESCRIPTION:In this talk\, I will present a joint work with Uwe Grimm\, Yas ushi Nagai and Petra Staynova based on a recent preprint: arXiv:2101.02056 . Regarding the Prouhet-Thue-Morse word as a two-colouring of the positive integers\, we look for long monochromatic arithmetic progressions occurri ng in the sequence.\n\nThe size of the longest arithmetic progression of d ifference $d=2^n-1$ was previously established by O. Parshina. Using a dif ferent approach\, mainly based on exploiting the substitution structure of the Prouhet-Thue-Morse word\, we will show how we can re-establish this r esult and find another series of long arithmetic progressions of differenc e d=2^n+1. Then\, we will comment on a generalisation of these results for a special class of bijective binary words\, and we will finish with some more general results and some open questions. URL:https://cow-seminar.github.io/archives/2021.html#20210322-aedo END:VEVENT BEGIN:VEVENT UID:20210322-dolce@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210322T150000Z DTEND:20210322T160000Z SUMMARY:Francesco Dolce: On morphisms preserving palindromic richness DESCRIPTION:A finite word is said to be rich if it has maximal number of pa lindromic factors (this is known to be the length of the word plus one). T his definition can be naturally extended to infinite words.Sturmian words and Rote complementary symmetric sequences form two classes of binary rich words\, while strict episturmian words and words coding symmetric interva l exchange transformations give us other examples on larger alphabets.\nIn this talk we study homomorphisms of the free monoid which allow to constr uct new rich words from already known rich words. In particular\, we focus on two types of morphisms: Arnoux-Rauzy morphisms and morphisms from Clas s $P_{ret}$. These morphisms contain Sturmian morphisms as a subclass. We show that Arnoux-Rauzy morphisms preserve the set of all rich words.\nWe a lso characterize $P_{ret}$ morphisms which preserve richness on binary alp habet.\nThis is a joint work with Edita Pelantová. URL:https://cow-seminar.github.io/archives/2021.html#20210322-dolce END:VEVENT BEGIN:VEVENT UID:20210322-shallit@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210322T153000Z DTEND:20210322T163000Z SUMMARY:Jeffrey Shallit: Robbins and Ardila meet Berstel DESCRIPTION:In this short talk I show how to obtain a result of Robbins and (later)\nArdila on partitions of integers in Fibonacci numbers\, and much more\,\nusing a 2001 transducer created by Jean Berstel. The "fun" part is\nthat once you have Berstel's transducer\, the rest follows by purely\ ncomputational means. URL:https://cow-seminar.github.io/archives/2021.html#20210322-shallit END:VEVENT BEGIN:VEVENT UID:20210322-frid@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210322T160000Z DTEND:20210322T170000Z SUMMARY:Anna E. Frid: The semigroup of trimmed morphisms DESCRIPTION:We start a study of possible orders of morphic images of words. In the binary case\, it is known that every morphism is either order-pres erving or order-reversing. For larger alphabets\, the situation can be muc h more complicated. URL:https://cow-seminar.github.io/archives/2021.html#20210322-frid END:VEVENT BEGIN:VEVENT UID:20210329-sakarovitch@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210329T130000Z DTEND:20210329T140000Z SUMMARY:Jacques Sakarovitch: From Fibonacci to golden mean representations DESCRIPTION:*\n\nEvery positive integer can be written as a sum of Fibonacc i numbers\; this yields a Fibonacci representation of the integer. A posit ive integer can also be written as a (finite) sum of (positive and negativ e) powers of the golden mean\; this yields a golden mean representation of the integer\, with the radix point roughly in the middle of the writing. It is the golden mean expansion when it contains no consecutive digits equ al to 1.\n\nWe show that there exists a letter-to-letter finite two-tape a utomaton that maps the Fibonacci representation of any positive integer on to its golden mean expansion\, provided the latter is folded around the ra dix point. As a corollary\, the set of golden mean expansions of the posi tive integers is a linear context-free language.\n\nThese results are gene ralised to the more general case of integer representations in numeration systems built upon quadratic Pisot units.\n\nJoint work with Christiane Fr ougny\, published in 1999 in the Journal of Algebra and Computation. This talk is a follow-up to the one of October 15 by Michel Dekking\, who kindl y quoted this paper but deemed it hard to understand. URL:https://cow-seminar.github.io/archives/2021.html#20210329-sakarovitch END:VEVENT BEGIN:VEVENT UID:20210412-goyheneche@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210412T130000Z DTEND:20210412T140000Z SUMMARY:Valérie Goyheneche: Eigenvalues and constant arithmetical progress ions for substitutive sequences DESCRIPTION:The main subject of this talk is to answer the following decida bility question : does a substitutive sequence $x$ admit a constant arithm etical progression $ (x_{k+np})_n $?\n\nOur method mainly relies on the li nk between constant arithmetical subsequences and (dynamical) eigenvalues of the underlying dynamical system.\nWe will explain a method to compute t he set of (additive) eigenvalues associated to such systems.\nWe can then deduce\, given an integer $p$\, if the sequence $x$ contains a constant ar ithmetical progression with period $p$.\nAt the end of the talk\, we will focus on the case of primitive constant-length substitutions\, for which t he set of such periods can be described by an automaton. URL:https://cow-seminar.github.io/archives/2021.html#20210412-goyheneche END:VEVENT BEGIN:VEVENT UID:20210426-zamboni@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210426T130000Z DTEND:20210426T140000Z SUMMARY:Luca Zamboni: Singular words DESCRIPTION:The extremal solutions to certain problems in the theory of fin ite continued fractions are characterised by a special combinatorial prope rty which we call the *singular* property. This property may be interprete d in the framework of finite words\, cyclic words\, and one and two-sided infinite words over arbitrary ordered alphabets. Each linear (resp. cyclic ) word w is Abelian equivalent to a singular linear (resp. cyclic) word w ’ which is in general unique up to reversal. We develop an algorithm fo r generating all singular words having a prescribed Parikh vector which is based in part on a non-commutative variant of the usual Euclidean algorit hm. This allows us to answer a question of G. Ramharter from 1983 on the e xtremal values of the regular and semi-regular cyclic continuants introduc ed by Motzkin and Straus in the 1950’s. We also confirm a conjecture of Ramharter in certain instances and exhibit counter examples in other cases . As for infinite words\, the singular property in the context of bi-infi nite binary words coincides with the Markoff property which was shown by C . Reutenauer to be equivalent to the balance property. We generalise this to higher alphabets by showing that the singular property is the fundame ntal property which characterises the language structure of codings of sym metric k-interval exchange transformations. This is based on a collaborat ion with Alessandro De Luca and Marcia Edson initiated during the first Co vid lockdown of 2020. URL:https://cow-seminar.github.io/archives/2021.html#20210426-zamboni END:VEVENT BEGIN:VEVENT UID:20210503-richomme@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210503T130000Z DTEND:20210503T140000Z SUMMARY:Gwenaël Richomme: On sets of indefinitely desubstitutable words DESCRIPTION:The stable set associated to a given set $S$ of nonerasing endo morphisms or substitutions is the set of all right infinite words that can be indefinitely desubstituted over $S$. This notion generalizes the notio n of sets of fixed points of morphisms. It is linked to $S$-adicity and to property preserving morphisms. Two main questions are considered. Which k nown sets of infinite words are stable sets? Which ones are stable sets of a finite set of substitutions? While bringing answers to the previous que stions\, some new way of characterizing several well-known sets of words s uch as the set of binary balanced words or the set of episturmian words ar e presented. A characterization of the set of nonerasing endomorphisms tha t preserve episturmian words is also provided. URL:https://cow-seminar.github.io/archives/2021.html#20210503-richomme END:VEVENT BEGIN:VEVENT UID:20210510-buzzard@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210510T130000Z DTEND:20210510T140000Z SUMMARY:Kevin Buzzard: Teaching computers to prove theorems DESCRIPTION:Over the last few years I have been teaching proofs of theorems to computers\, and teaching students how to teach proofs of theorems to c omputers. The Kruskal Katona theorem is a theorem I learnt as an MSc stude nt\, and Cambridge PhD student Bhavik Mehta taught it to the Lean theorem prover here: https://b-mehta.github.io/combinatorics/ . Lean's maths libra ry `mathlib` https://github.com/leanprover-community/mathlib is now half a million lines of theorem proofs\, many of them proved by mathematicians w ho have picked up this language\, and most of them learnt it like Bhavik\, just choosing a project and working on it. I will talk about how I learnt Lean\, how you can learn Lean\, what the point of learning Lean is\, what the point of teaching Lean is\, and where all this stuff might end up goi ng. Rest assured -- I will not assume any prior familiarity with computer theorem provers in this talk! URL:https://cow-seminar.github.io/archives/2021.html#20210510-buzzard END:VEVENT BEGIN:VEVENT UID:20210517-shallit@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210517T130000Z DTEND:20210517T140000Z SUMMARY:Jeffrey Shallit: The Walnut Tutorial: Using A Tool for Doing Combin atorics on Words DESCRIPTION:Walnut is free open-source software\, written by Hamoon Mousavi \, that can\nrigorously prove or disprove claims about automatic sequences (broadly\nunderstood)\, such as the Thue-Morse sequence\, the Fibonacci i nfinite\nword\, and others. It can also be used to create explicit formul as for\nvarious aspects of such sequences\, such as subword complexity\,\n palindrome complexity\, and so forth.\n\nIn this talk I won't discuss how it works. Instead I'll give a\ntutorial\, surveying the kinds of things you can and can't do with it.\nWe'll "get our hands dirty" and solve probl ems in real time.\n\nAt the end\, if there's time\, I'll solicit problems about such sequences\nfrom the audience and try to solve them with Walnut. Come prepared with\nsome conjecture you haven't been able to prove yet!\ n\nThe tutorial lasts about 90 minutes. URL:https://cow-seminar.github.io/archives/2021.html#20210517-shallit END:VEVENT BEGIN:VEVENT UID:20210531-moutot@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210531T130000Z DTEND:20210531T140000Z SUMMARY:Etienne Moutot: Recent advances around Nivat's conjecture DESCRIPTION:Nivat's conjecture states that any two dimensional word with "l ow enough" pattern complexity must be periodic.\nEven if the statement of the conjecture is quite simple and very similar to the one dimensional Mor se-Hedlund theorem\, the conjecture is still open since stated by Maurice Nivat in 1997. However\, there have been a lot of progress towards a proof in the last five years\, and many new tools started to emerge. In 2015\, Cyr and Kra started to use tools from symbolic dynamics to improve the bou nd required to prove periodicity. At about the same time\, Jarkko Kari and Michal Szabados started to develop an algebraic approach to tackle the co njecture\, leading to very elegant proofs of new results related to Nivat' s conjecture.\n\nIn this talk I will present the conjecture and some of th e last results around it. I will then focus on the algebraic approach init iated by Kari and Szabados. URL:https://cow-seminar.github.io/archives/2021.html#20210531-moutot END:VEVENT BEGIN:VEVENT UID:20210607-ochem@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210607T130000Z DTEND:20210607T140000Z SUMMARY:Pascal Ochem: Avoiding large squares in trees and planar graphs DESCRIPTION:The Thue number $T(G)$ of a graph $G$ is the minimum number of colors needed to color $G$ without creating a square on a path of $G$. For a graph class $C$\, $T(C)$ is the supremum of $T(G)$ over the graphs $G$ in $C$.\nThe Thue number has been investigated for famous minor-closed cla sses:\n$T(tree) = 4$\, $7 \\leq T(outerplanar) \\leq 12$\, $11 \\leq T(p lanar) \\leq 768$.\nFollowing a suggestion of Grytczuk\, we consider the g eneralised parameters $T_k(C)$ such that only squares of period at least $ k$\nmust be avoided. Thus\, $T(C) = T_1(C)$.\nWe show that $T_2(tree) = 3$ \, $T_5(tree) = 2$\, and $T_k(planar) \\geq 11$ for every fixed $k$.\nThis is a joint work with Daniel Gonçalves and Matthieu Rosenfeld. URL:https://cow-seminar.github.io/archives/2021.html#20210607-ochem END:VEVENT BEGIN:VEVENT UID:20210614-badkobeh@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210614T130000Z DTEND:20210614T140000Z SUMMARY:Golnaz Badkobeh: Left Lyndon tree construction DESCRIPTION:We extend the left-to-right Lyndon factorisation of a word to t he left Lyndon tree construction of a Lyndon word. It yields an algorithm to sort the prefixes of a Lyndon word according to the infinite ordering d efined by Dolce et al. (2019). A straightforward variant computes the left Lyndon forest of a word. All algorithms run in linear time in the letter- comparison model. URL:https://cow-seminar.github.io/archives/2021.html#20210614-badkobeh END:VEVENT BEGIN:VEVENT UID:20210621-byszewski@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210621T130000Z DTEND:20210621T140000Z SUMMARY:Jakub Byszewski: Automata and finite order automorphisms of the pow er series ring DESCRIPTION: URL:https://cow-seminar.github.io/archives/2021.html#20210621-byszewski END:VEVENT BEGIN:VEVENT UID:20210621-duda@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210621T133000Z DTEND:20210621T143000Z SUMMARY:Jarosław Duda: Generalized Fibonacci coding problem using Maximal Entropy Random Walk and Asymmetric Numeral Systems DESCRIPTION:In Fibonacci coding we forbid '11' patterns\, bringing question of generalization to more complex constraints. I will very briefly presen t how to practically handle such general situation\, including 2D lattice (hard square problem)\, with motivation e.g. to increase capacity of hard disk. We will first find probability distribution of patterns in such ense mble of sequences\, which can be obtained with MERW ( https://en.wikipedia .org/wiki/Maximal_entropy_random_walk ). Then we can use entropy coder - f or this purpose I have introduced ANS ( https://en.wikipedia.org/wiki/Asym metric_numeral_systems ): generalization of numeral systems to optimize fo r a chosen probability distribution of digits. I will also briefly present its two widely used variants: rANS with multiplication - now e.g. in JPEG XL image format\, or tANS building finite state automaton for a given pro bability distribution - now used e.g. in Facebook Zstandard or Apple LZFSE compressors. URL:https://cow-seminar.github.io/archives/2021.html#20210621-duda END:VEVENT BEGIN:VEVENT UID:20210621-peltomaki@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210621T140000Z DTEND:20210621T150000Z SUMMARY:Jarkko Peltomäki: Initial nonrepetitive complexity of regular epis turmian words and their Diophantine exponents DESCRIPTION: URL:https://cow-seminar.github.io/archives/2021.html#20210621-peltomaki END:VEVENT BEGIN:VEVENT UID:20210621-pandoh@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210621T143000Z DTEND:20210621T153000Z SUMMARY:Palak Pandoh: Counting scattered palindromes in a finite word DESCRIPTION: URL:https://cow-seminar.github.io/archives/2021.html#20210621-pandoh END:VEVENT BEGIN:VEVENT UID:20210621-lagisquet@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210621T150000Z DTEND:20210621T160000Z SUMMARY:Clément Lagisquet: On Markov Numbers: An answer to three conjectur es from Aigner DESCRIPTION: URL:https://cow-seminar.github.io/archives/2021.html#20210621-lagisquet END:VEVENT BEGIN:VEVENT UID:20210621-pawlik@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210621T153000Z DTEND:20210621T163000Z SUMMARY:Bartłomiej Pawlik: Nonchalant procedure DESCRIPTION: URL:https://cow-seminar.github.io/archives/2021.html#20210621-pawlik END:VEVENT BEGIN:VEVENT UID:20210628-manea@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210628T130000Z DTEND:20210628T140000Z SUMMARY:Florin Manea: Combinatorial algorithms for subsequences DESCRIPTION:In this talk\, we will cover a series of recent algorithmic res ults related to the processing of subsequences occurring in words. Firstly \, we will show how to test in linear time whether two given words have ex actly the same set of subsequences of length $k$ (or\, in other words\, wh ether they are $k$-equivalent w.r.t. the Simon congruence)\, where $k$ is a positive integer also given as input. Secondly\, we show how to compute in linear time\, for two given words\, which is the largest positive integ er $k$ for which the two words are $k$-Simon-congruent. We will conclude t his talk with a series of related results. On the one hand\, we consider t he problem of transforming words by edit operations so that they become Si mon-congruent and\, on the other hand\, we consider the notion of absent s ubsequences in words and problems related to this. URL:https://cow-seminar.github.io/archives/2021.html#20210628-manea END:VEVENT BEGIN:VEVENT UID:20210712-holub@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210712T130000Z DTEND:20210712T140000Z SUMMARY:Štěpán Holub: Using Isabelle/HOL in Combinatorics on Words resea rch DESCRIPTION:In this talk I will introduce a (growing) library of results in Combinatorics on Words formalized in the proof assistant Isabelle/HOL. I will emphasize the practical use of this library by a beginner\, rather th an theoretical aspects of either the proof assistant or the formalized res ults. The participants are therefore strongly encouraged to try Isabelle a long with me during my talk\, which requires to have Isabelle installed\, as well as the draft version of our formalization downloaded. Questions st emming from your own attempts are most welcome\, independently of how naï ve they may seem.\n\nFor an installation guide\, visit\nhttps://gitlab.com /formalcow/combinatorics-on-words-formalized#a-short-guide-for-isabellehol -beginners-how-to-formalize-your-combinatorics-on-words-result\nEverything should be straightforward. If you encounter any problem\, you can write m e to holub@karlin.mff.cuni.cz.\nIssues with the installation can be also a ddressed during the preliminary technical session: I will be available 20 minutes before the official start. URL:https://cow-seminar.github.io/archives/2021.html#20210712-holub END:VEVENT BEGIN:VEVENT UID:20210726-bell@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210726T130000Z DTEND:20210726T140000Z SUMMARY:Jason Bell: Lie complexity of words DESCRIPTION:Given a right-infinite word $\\bf{w}$ over a finite alphabet\, we introduce a new complexity function $L_{\\bf w}(n)$\, motivated by the theory of Lie algebras\, whose value at $n$ is the number of equivalence c lasses of factors $x$ of ${\\bf w}$ of length $n$ with the property that e very cyclic permutation of $x$ is again a factor of ${\\bf w}$\, where two words $x$ and $y$ are equivalent if there exist words $a$ and $b$ such th at $x=ab$ and $y=ba$. We show that the Lie complexity function is uniform ly bounded for words ${\\bf w}$ of linear factor complexity and that it is a $k$-automatic sequence when ${\\bf w}$ is $k$-automatic. As a conseque nce of these results we can show that if ${\\bf w}$ is a word of linear fa ctor complexity then there are only finitely many primitive factors $v$ of ${\\bf w}$ with the property that $v^n$ is a factor of ${\\bf w}$ for eve ry $n\\ge 1$. We also consider extensions of these results. This is join t work with Jeffrey Shallit. URL:https://cow-seminar.github.io/archives/2021.html#20210726-bell END:VEVENT BEGIN:VEVENT UID:20210927-shur@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20210927T130000Z DTEND:20210927T140000Z SUMMARY:Arseny Shur: Abelian repetition threshold revisited DESCRIPTION:Abelian repetition threshold ART$(k)$ is the number separating fractional Abelian powers which are avoidable and unavoidable over the $k$ -letter alphabet. In contrast with the «usual» repetition threshold RT$( k)$\, no exact values of ART$(k)$ are known. The lower bounds were proved in [A.V. Samsonov\, A.M. Shur. On Abelian repetition threshold. RAIRO ITA\ , 2012] and conjectured to be tight. We present a method of study of Abeli an power-free languages using random walks in prefix trees and some experi mental results obtained by this method. On the base of these results\, we conjecture that the lower bounds for ART$(k)$ by Samsonov and Shur are not tight for all $k$ except for $k=5$ and prove this conjecture for $k=6\,7\ ,8\,9\,10$. Namely\, we show that ART$(k)>(k-2)(k-3)$ in all these cases. URL:https://cow-seminar.github.io/archives/2021.html#20210927-shur END:VEVENT BEGIN:VEVENT UID:20211011-gheeraert@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20211011T130000Z DTEND:20211011T140000Z SUMMARY:France Gheeraert: $S$-adic characterization of dendric languages: t ernary case DESCRIPTION:Uniformly recurrent dendric languages generalize Arnoux-Rauzy l anguages and interval exchanges and are defined via the left-\, right- and biextensions of their words. In a series of articles\, Berthé et al. int roduced them and\, among other results\, proved that this family is stable under derivation\, which leads to the existence of particular $S$-adic re presentations.\n\nIn this talk\, we will see how we can use the properties of these representations to obtain an $S$-adic characterization of unifor mly recurrent dendric languages. We give some general results then focus o n the case of a ternary alphabet to obtain a simpler characterization.\n\n This is a joint work with Marie Lejeune and Julien Leroy. URL:https://cow-seminar.github.io/archives/2021.html#20211011-gheeraert END:VEVENT BEGIN:VEVENT UID:20211025-durand@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20211025T130000Z DTEND:20211025T140000Z SUMMARY:Fabien Durand: Beyond substitutive sequences : Self-induced dynamic al systems and sequences on compact alphabets DESCRIPTION:It is well-known that primitive substitutions are recognizable. This property implies that the minimal substitution subshifts $(X\,S)$ ar e self-induced. That is\, there exists a clopen set $U$ included in $X$ su ch that $(U\,S_U)$ is isomorphic to $(X\,S)$\, where $S_U (x)=S^n (x)$ and $n>0$ is the first iterate coming back to $U$.\n\nWe will see that all dy namical systems are self-induced in a measurable perspective.\n\nBut from a topological point of view self induction characterizes minimal substitut ion subshifts on possibly infinite alphabets (even uncountable). URL:https://cow-seminar.github.io/archives/2021.html#20211025-durand END:VEVENT BEGIN:VEVENT UID:20211108-rust@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20211108T140000Z DTEND:20211108T150000Z SUMMARY:Dan Rust: Random substitutions DESCRIPTION:A random substitution is a generalisation of a substitution on a finite alphabet. Whereas with classical substitutions\, letters have a s ingle word as an image\, random substitutions have a finite set of possibl e image words that are independently chosen each time it is applied to the letters in a word. As an example\, the `random Fibonacci substitution' is given by\n\n$$ a \\mapsto \\{ab\,ba\\}\, b \\mapsto \\{a\\}.$$\n\nThis gi ves rise to languages of legal words that share similar properties with su bstitutive words (i.e.\, hierarchical structures) but which also have expo nential complexity functions (entropy). I will give an overview of this ra rely explored class of systems\, some of the aspects that have recently be en studied\, and some easy-to-state open problems. URL:https://cow-seminar.github.io/archives/2021.html#20211108-rust END:VEVENT BEGIN:VEVENT UID:20211122-kucherov@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20211122T140000Z DTEND:20211122T150000Z SUMMARY:Gregory Kucherov: Minimizers and one question about de Bruijn graph s DESCRIPTION: URL:https://cow-seminar.github.io/archives/2021.html#20211122-kucherov END:VEVENT BEGIN:VEVENT UID:20211122-shallit@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20211122T143000Z DTEND:20211122T153000Z SUMMARY:Jeffrey O. Shallit: Abelian cubes and additive cubes in the Tribona cci word DESCRIPTION:In this short talk I show how to obtain a result of Robbins and (later)\nArdila on partitions of integers in Fibonacci numbers\, and much more\,\nusing a 2001 transducer created by Jean Berstel. The "fun" part is\nthat once you have Berstel's transducer\, the rest follows by purely\ ncomputational means. URL:https://cow-seminar.github.io/archives/2021.html#20211122-shallit END:VEVENT BEGIN:VEVENT UID:20211122-grytczuk@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20211122T144500Z DTEND:20211122T154500Z SUMMARY:Jarosław Grytczuk: Twins in permutations DESCRIPTION:A pair of disjoint subsequences in a permutation having the sam e relative order is called twins. How long twins must occur in every permu tation of length n?\nThe shape of a sequence of distinct integers is a bin ary sequence of signs of differences of consecutive terms of the sequence. A pair of disjoint subsequences in a permutation having the same shape is called weak twins. How long weak twins must occur in every permutation of length n?\nI will present some results and conjectures concerning the abo ve questions. URL:https://cow-seminar.github.io/archives/2021.html#20211122-grytczuk END:VEVENT BEGIN:VEVENT UID:20211122-gabric@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20211122T151500Z DTEND:20211122T161500Z SUMMARY:Daniel Gabric: Words that almost commute DESCRIPTION:The *Hamming distance* $\\text{ham}(u\,v)$ between two equal-l ength words $u$\, $v$ is the number of positions where $u$ and $v$ differ. The words $u$ and $v$ are said to be *conjugates* if there exist non-empt y words $x\,y$ such that $u=xy$ and $v=yx$. The smallest value $\\text{ham }(xy\,yx)$ can take on is $0$\, when $x$ and $y$ commute. But\, interestin gly\, the next smallest value $\\text{ham}(xy\,yx)$ can take on is $2$ and not $1$. We provide an efficient formula to count the number $h(n)$ of le ngth-$n$ words $u=xy$ over a $k$-letter alphabet that have a conjugate $v= yx$ such that $\\text{ham}(xy\,yx)=2$. We also provide efficient formulae for other quantities closely related to $h(n)$. Finally\, we give some res ults on the asymptotic behaviour of $h(n)$. URL:https://cow-seminar.github.io/archives/2021.html#20211122-gabric END:VEVENT BEGIN:VEVENT UID:20211206-fici@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20211206T140000Z DTEND:20211206T150000Z SUMMARY:Gabriele Fici: Some Remarks on Automatic Sequences\, Toeplitz words and Perfect Shuffling DESCRIPTION:One of the many nice properties of the Thue-Morse sequence $t = 0110100110010110\\cdots$ is that t is equal to the perfect shuffling of i tself with its binary complement $(1-t)$\, i.e.\, it can be defined by mea ns of the equation $t = t ⧢ (1 − t)$. In general\, for any automatic sequence $w$\, there exist two automatic sequences $w'$ and $w’’$ such that $w = w' ⧢ w''$. We call the sequences $w’$ and $w’’$ the ev en and the odd part of $w$\, respectively. We will exhibit some curious fa cts about this decomposition for some (more or less) known 2- and 3-automa tic sequences.\n\n[Follow-up with some answers](https://arxiv.org/pdf/2112 .12125.pdf) URL:https://cow-seminar.github.io/archives/2021.html#20211206-fici END:VEVENT BEGIN:VEVENT UID:20211220-konieczny@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20211220T140000Z DTEND:20211220T150000Z SUMMARY:Jakub Konieczny: Finitely-valued generalised polynomials DESCRIPTION:Generalised polynomials are expressions constructed from polyno mials with the use of the floor function\, addition and multiplication\, s uch as $\\lfloor \\sqrt{2} n \\lfloor \\sqrt{3} n^2\\rfloor + \\sqrt{6} + \\frac{1}{2}\\rfloor$. Despite superficial similarity\, generalised polyno mials exhibit many phenomena which are impossible for ordinary polynomials . In particular\, there exist generalised polynomial sequences which take only finitely many values but are not constant. This is the case\, for ins tance\, for Sturmian sequences.\n\nIn my talk\, I will discuss finitely-va lued generalised polynomial sequences from the perspective of combinatoric s on words. The talk will include a survey of existing results on generali sed polynomials\, adapted to the current context\, as well as several new results obtained in joint works with Boris Adamczewski and with Jakub Bysz ewski. URL:https://cow-seminar.github.io/archives/2021.html#20211220-konieczny END:VEVENT BEGIN:VEVENT UID:20220110-dvorakova@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220110T140000Z DTEND:20220110T150000Z SUMMARY:Lubomíra Dvořáková: On minimal critical exponent of balanced se quences DESCRIPTION:The conjecture stated by Rampersad\, Shallit and Vandomme says that the minimal critical exponent of balanced sequences over the alphabet of size $d>4$ equals $(d-2)/(d-3)$. This conjecture is known to hold for $d=5\, 6\, 7\, 8\, 9\, 10$.\n\nIn this talk\, we will describe in more det ails the ideas and the techniques used to refute this conjecture by showin g that the picture is different for bigger alphabets. We prove that critic al exponents of balanced sequences over an alphabet of size $d>10$ are lo wer bounded by $(d-1)/(d-2)$ and this bound is attained for all even numbe rs $d>10$.\n\nAccording to this result\, we conjecture that the least crit ical exponent of a balanced sequence over $d$ letters is $(d-1)/(d-2)$ for all $d>10$. URL:https://cow-seminar.github.io/archives/2022.html#20220110-dvorakova END:VEVENT BEGIN:VEVENT UID:20220124-whiteland@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220124T140000Z DTEND:20220124T150000Z SUMMARY:Markus Whiteland: On some decidable properties of discrete-time lin ear dynamical systems DESCRIPTION:A discrete-time linear dynamical system (LDS) $(A\,x)$ is the o rbit of a point $x \\in \\mathbb{R}^d$ under a linear map $A\\colon \\math bb{R}^d \\to \\mathbb{R}^d$. In this talk we consider decision problems on LDS arising from program verification\, such as reachability problems: gi ven a LDS $(A\,x)$ and a semi-algebraic target set $T \\in \\mathbb{R}^d$\ , does the orbit intersect $T$? It is well-known that such questions quick ly lead to open problems\, such as Skolem's problem on linear recurrence s equences. We identify the borderline between hard instances and decidable instances with respect to the dimension of the target set $T$. The methods used in the decidable cases quickly give rise to symbolic dynamical syste ms over which we have a lot of control: this allows us to go beyond mere r eachability to deciding $\\omega$-regular properties of the LDS with respe ct to a low-dimensional target set $T$.\n\nJoint work with C. Baier\, F. F unke\, S. Jantsch\, T. Karimov\, E. Lefaucheux\, F. Luca\, J. Ouaknine\, D . Purser\, A. Varonka\, and J. Worrell. URL:https://cow-seminar.github.io/archives/2022.html#20220124-whiteland END:VEVENT BEGIN:VEVENT UID:20220207-dekking@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220207T140000Z DTEND:20220207T150000Z SUMMARY:Michel Dekking: Combinatorics of Fibonacci and golden mean number r epresentations DESCRIPTION:How many ways are there to represent a number as a sum of power s of the golden mean? Among these\, what is the best way to do this? What is the relation with representing a number as a sum of Fibonacci numbers? I will give some answers to these questions in my talk. URL:https://cow-seminar.github.io/archives/2022.html#20220207-dekking END:VEVENT BEGIN:VEVENT UID:20220221-moutot@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220221T140000Z DTEND:20220221T150000Z SUMMARY:Etienne Moutot: Pattern complexity of 2D substitutive shifts DESCRIPTION:In this presentation\, I will talk about pattern complexity of two-dimensional substitutive shifts. More precisely\, I will focus on lowe r bounds on the complexity of **aperiodic** 2D substitutive shifts.\n\n*Pa ttern complexity* consists in counting the number of different mxn rectang ular patterns that appear in an infinite coloring of $\\mathbb Z^2$ or in a shift space. A corollary of our recent work with Jarkko Kari on Nivat's conjecture [1] shows that any aperiodic subshift have pattern complexity a t least $mn+1$ for all $m$ and $n$.\n\nWith Coline Petit-Jean we have been trying to improve this lower bound for a particular class of shift spaces : substitutive shifts. For some substitutions (*primitive* and *marked* su bstitutions)\, we show that if their shift space is aperiodic\, then it ha s complexity at least $C*mn$\, with $C>1$ a constant depending on the subs titution. I will also talk briefly about non-marked substitutions and why our current proof does not apply to them\, even if we believe that a simil ar result might still hold.\n\n[1] Decidability and Periodicity of Low Com plexity Tilings. Jarkko Kari\, Etienne Moutot\, Theory of Computing System s\, 2021 URL:https://cow-seminar.github.io/archives/2022.html#20220221-moutot END:VEVENT BEGIN:VEVENT UID:20220307-allouche@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220307T140000Z DTEND:20220307T150000Z SUMMARY:Jean-Paul Allouche: Thue and 7-3 DESCRIPTION:March 7\, 2022 (in French 7/3) is the 100th anniversary of the death of Axel Thue.\nHe was a Norwegian mathematician\, principally known for his work in Diophantine\napproximation\, but he is also known for his work in combinatorics.\n\nWe will speak a little of his number-theoretic p apers\, and more about his contribution\nin combinatorics\, essentially re stricting ourselves to the --ubiquitous-- Thue-Morse\nor Prouhet-Thue-Mors e sequence. We will try to survey not only some well-known\nfeatures of th is sequence\, but also less classical properties: one of these\nis an occu rrence of... 7/3 for this sequence\, the other is about Shogi (将棋)\,\n or Japanese chess\, and the Sennichite (千日手) (a new rule decided aft er a play\ndated March... 8\, 1983).\n\nTo conclude this abstract\, we do not resist to give a quote of Thue:\n"The further removed from usefulness or practical application\, the more important."\nRemoved from practical ap plication? one might want to look at the definition of the\nprogramming la nguage "Thue" that Wikipedia describes as follows:\n"Thue is an esoteric p rogramming language invented by John Colagioia in early 2000.\nIt is a met a-language that can be used to define or recognize Type-0 languages from\n the Chomsky hierarchy. Because it is able to define languages of such comp lexity\,\nit is also Turing-complete itself. Thue is based on a nondetermi nistic string\nrewriting system called semi-Thue grammar\, which itself is named after the Norwegian\nmathematician Axel Thue." URL:https://cow-seminar.github.io/archives/2022.html#20220307-allouche END:VEVENT BEGIN:VEVENT UID:20220321-rampersad@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220321T140000Z DTEND:20220321T150000Z SUMMARY:Narad Rampersad: Applications of Walnut to problems of local period icity DESCRIPTION:There are a number of natural choices for measuring the local\n periodicity at a given position $i$ of an infinite word: for instance\,\no ne could consider repetitions 1) ending at position $i$\; 2) starting\nat position $i$\; or 3) centered at position $i$. With regards to\noption 1) \, it is known that aperiodic infinite words cannot have all\nsufficiently large prefixes end with cubes. It is natural then to ask\nfor such words how many prefixes can end with cubes. Using Walnut\, we\nobtain a charac terization of these prefixes for the Fibonacci word.\nRegarding option 3)\ , Mignosi and Restivo introduced an interesting\ncomplexity measure: $h_{\ \bf w}(n)$\, which is the average of the local\nperiods over the first $n$ positions of ${\\bf w}$. Again using\nWalnut\, we estimate the asymptoti c behaviour of this function for some\n2-automatic sequences\, such as the Thue-Morse sequence\, the\nRudin-Shapiro sequence\, and the period-doubli ng sequence. URL:https://cow-seminar.github.io/archives/2022.html#20220321-rampersad END:VEVENT BEGIN:VEVENT UID:20220404-defant@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220404T130000Z DTEND:20220404T140000Z SUMMARY:Colin Defant: Anti-powers in Aperiodic Recurrent Words DESCRIPTION:In 2016\, Fici\, Restivo\, Silva\, and Zamboni introduced the n otion of a $k$-anti-power\, which is a word of the form $w_1 \\cdots w_k$\ , where $w_1\,\\ldots\,w_k$ are words of the same length that are all dist inct. I will begin by reviewing the main results that these authors proved about anti-powers. I will then discuss anti-powers appearing as factors i n the Thue-Morse word. This will lead into a discussion of anti-powers in aperiodic recurrent words and aperiodic morphic words. URL:https://cow-seminar.github.io/archives/2022.html#20220404-defant END:VEVENT BEGIN:VEVENT UID:20220425-reutenauer@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220425T130000Z DTEND:20220425T140000Z SUMMARY:Christophe Reutenauer: Constructions and parametrization of conjuga tes of Christoffel words DESCRIPTION:Following a recent work of Michel Laurent and the first author\ , we propose a deformation of the Rauzy rules (equivalently of the de Luca construction of standard words) in order to construct all conjugates of a ll Christoffel words (equivalently of all standard words). This constructi on is based on integer legal Ostrowski representations\, following Frid. T he constructed word depends only the represented integer (and even works in the free group\, up to conjugation however). Choosing greedy representa tions\, we determine of the longest border of conjugates\, thereby recover ing results of Lapointe on the smallest periods. Choosing the lazy represe ntation\, we may revisit the Sturmian graph of Epifanio\, Frougny\, Gabrie le\, Mignosi and Shallit\; in particular we show that this graph is essen tially a subgraph of the Stern-Brocot tree\, and that the compact graph (w hich is a compaction of the minimal automaton of the set of suffixes of a central word) is similarly embedded in the tree of central words of Aldo d e Luca. URL:https://cow-seminar.github.io/archives/2022.html#20220425-reutenauer END:VEVENT BEGIN:VEVENT UID:20220516-barro@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220516T130000Z DTEND:20220516T140000Z SUMMARY:Moussa Barro: Billard dans le cube DESCRIPTION:On considère le billard dans un cube. On code une trajectoire par les faces rencontrées. Le but de l'exposé sera de décrire le langag e d'un tel mot dans le cas ou l'orbite n'est pas dense. URL:https://cow-seminar.github.io/archives/2022.html#20220516-barro END:VEVENT BEGIN:VEVENT UID:20220530-tahay@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220530T130000Z DTEND:20220530T140000Z SUMMARY:Pierre-Adrien Tahay: Column representation of words in cellular aut omata DESCRIPTION:The task of representing a sequence over a finite alphabet in t he space-time\ndiagram of a cellular automaton is a non-trivial and still not entirely explored\ntopic. One of the first results on the subject was done by Fischer in 1965 with a construction of the characteristic sequence of primes numbers. Many results and improvements have been established si nce. In 2015\, Rowland and Yassawi showed that there is a close connection between the $p$-automatic sequences and the linear cellular automata. Mor e precisly the columns of linear cellular automata are $p$-\nautomatic seq uences and all $p$-automatic sequences can be realized by some linear cell ular automata with memory. Moreover their proof is constructive. In 2018\, Marcovici\, Stoll and Tahay investigated some constructions for nonautoma tic sequences such as the characteristic sequences of polynomials and the Fibonacci word.\n\nIn this talk I will present recent results obtained in collaboration with Francesco Dolce where we generalized the construction f or the Fibonacci word in a column of a cellular automaton\, to any Sturmia n word with quadratic slope. Our proof is constructive and use the ultimat e periodicity of the continued fraction expansion of the slope of the word . URL:https://cow-seminar.github.io/archives/2022.html#20220530-tahay END:VEVENT BEGIN:VEVENT UID:20220613-basic@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220613T130000Z DTEND:20220613T140000Z SUMMARY:Kristina Ago and Bojan Bašić: Some recent results on two "palindr omicity" measures DESCRIPTION:Various measures of the degree of "palindromicity" of a given w ord have been defined in the literature. In this talk we present some of o ur results concerning two such measures. The first one is the so-called *p alindromic defect* (or only *defect*). Let $|\\mathrm{Pal}(w)|$ denote the number of palindromic factors of a word $w$. The palindromic defect of $w $ is defined by $|w|+1-|\\mathrm{Pal}(w)|$ (it can be proved that this val ue is always nonnegative). This definition can be naturally extended to in finite words. While infinite words whose defect is zero (called *rich*) ha ve been researched quite much\, there are noticeably less results in the l iterature on infinite words of finite positive defect. In the first part o f the talk we introduce a construction of an infinite family of infinite w ords whose defect is finite and in many cases positive (with fully charact erized cases when the defect is $0$)\, and we analyze their properties. Ea ch of those words is either periodic (which is a less interesting case\, a nd explicitly characterized)\, or recurrent but not uniformly recurrent. E xamples of explicit constructions of such words that are not uniformly rec urrent have been quite deficient in the literature so far.\n\nThe second p art of talk is devoted to the so-called *MP-ratio*. The concept of MP-rati o is based on palindromic subwords (and not factors) of a given finite wor d. Call a word over an $n$-ary alphabet *minimal-palindromic* if it does n ot contain palindromic subwords of length greater than $\\big\\lceil\\frac {|w|}n\\big\\rceil$. The *MP-ratio* of a given $n$-ary word $w$ is defined as the quotient $\\frac{|rws|}{|w|}$\, where $r$ and $s$ are words such t hat the word $rws$ is minimal-palindromic and that the length $|r|+|s|$ is minimal possible. In order for the MP-ratio to be well-defined\, it has t o be shown that such a pair $(r\,s)$ always exist. It has been known for s ome time that this is true in the binary case\, but this question becomes much more complicated for larger arities. In this talk we show that the MP -ratio is well-defined for any arity\, and we present some further results on this topic. URL:https://cow-seminar.github.io/archives/2022.html#20220613-basic END:VEVENT BEGIN:VEVENT UID:20220620-domenech@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220620T130000Z DTEND:20220620T140000Z SUMMARY:Antoine Domenech: Avoiding doubled patterns DESCRIPTION:A pattern $P$ is $k$-avoidable if there exists\nan infinite wor d over $k$ letters that contains no occurrence of $P$.\nA pattern is doubl ed if all its variables appear at least twice.\nIt is known that doubled p atterns are 3-avoidable and it is conjectured\nthat only a finite number o f doubled patterns are not 2-avoidable.\nWe show that square-free doubled patterns with at most 4 variables are 2-avoidable.\nThen\, for each patter n doubled $P$ with at most 3 variables that is\nnot 2-avoidable\, we deter mine the minimum number of distinct\noccurrences of $P$ that are contained in an infinite binary word. URL:https://cow-seminar.github.io/archives/2022.html#20220620-domenech END:VEVENT BEGIN:VEVENT UID:20220627-popoli@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220627T130000Z DTEND:20220627T140000Z SUMMARY:Pierre Popoli: Maximum order complexity for some automatic and morp hic sequences along polynomial values DESCRIPTION:Automatic sequences are not suitable sequences for cryptographi c\napplications since both their subword complexity and their expansion\nc omplexity are small\, and their correlation measure of order 2 is\nlarge. These sequences are highly predictable despite having a large\nmaximum ord er complexity. However\, recent results show that polynomial\nsubsequences of automatic sequences\, such as the Thue-Morse sequence\nor the Rudin-Sh apiro sequence\, are better candidates for pseudorandom\nsequences. A natu ral generalization of automatic sequences are morphic\nsequences\, given b y a fixed point of a prolongeable morphism that is\nnot necessarily unifor m. In this talk\, I will present my results on\nlowers bounds for the maxi mum order complexity of the Thue-Morse\nsequence\, the Rudin-Shapiro seque nce and the sum of digits function in\nZeckendorf base\, which are respect ively automatics and morphic\nsequences. URL:https://cow-seminar.github.io/archives/2022.html#20220627-popoli END:VEVENT BEGIN:VEVENT UID:20220711-chase@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220711T130000Z DTEND:20220711T140000Z SUMMARY:Zachary Chase: The separating words\, $k$-deck\, and trace reconstr uction problems DESCRIPTION:What is the smallest size of a DFA that can separate two\ngiven strings of length $n$? Can two distinct strings of length $n$ have\nthe s ame multiset of subsequences of length $n^{1/3}$? How many random\nsubsequ ences of length $n/2$ of an unknown string $x$ of length $n$ do you\nneed to determine $x$ with high probability? We discuss these three\nproblems\, each having an exponential gap between the best known upper\nand lower bo unds\, and touch upon how they might be more related than\none might expec t. URL:https://cow-seminar.github.io/archives/2022.html#20220711-chase END:VEVENT BEGIN:VEVENT UID:20220919-shuo@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20220919T130000Z DTEND:20220919T140000Z SUMMARY:Shuo Li: On the number of squares in a finite word DESCRIPTION:A conjecture of Fraenkel and Simpson states that the number of distinct squares in a finite word $w$ is bounded by its length. In this ta lk\, we will review this conjecture from the perspective of the topologica l proprieties of the Rauzy graphs of $w$. We prove this conjecture by givi ng a stronger statement: the number of distinct squares in a finite word $ w$ is bounded by the length of $w$ minus the number of distinct letters in $w$. URL:https://cow-seminar.github.io/archives/2022.html#20220919-shuo END:VEVENT BEGIN:VEVENT UID:20221003-fokkink@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20221003T130000Z DTEND:20221003T140000Z SUMMARY:Robbert Fokkink: A few words on games DESCRIPTION:An impartial combinatorial game involves a set of positions tha t are either won or lost for the player that moves next. These are the so- called N-positions. If you know the set of N-positions\, then you have sol ved the game. Members of our community will immediately wonder if the char acteristic sequence of the set of N-positions form a word. It turns out th at Fibonacci word gives the set of N-positions in Wythoff Nim. Eric Duchen e and Michel Rigo found other examples of impartial games that are given b y words\, initiating ongoing work on the link between words and games. In this talk I will show how a modification of Wythoff Nim can be described b y the Tribonacci word. This is joint work with Dan Rust and Cisco Ortega. URL:https://cow-seminar.github.io/archives/2022.html#20221003-fokkink END:VEVENT BEGIN:VEVENT UID:20221017-romana@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20221017T130000Z DTEND:20221017T140000Z SUMMARY:Giuseppe Romana: String Attractor: a Combinatorial object from Data Compression DESCRIPTION:Very recently\, Kempa and Prezza [STOC 2018] introduced the not ion of String Attractor in the field of Data Compression\, and showed how this concept was already implicit in many other well known compression sch emes.\nBasically\, a String Attractor $\\Gamma$ of a finite word $w$ is a set of positions in $w$ such that each distinct factors that occurs in $w$ has at least an occurrence that crosses a position $j \\in \\Gamma$.\nIn this talk\, we explore String Attractors from a combinatorial perspective. \nWe discuss how the size $\\gamma^*$ of a string attractor of minimum siz e is affected when some classical combinatorial operations are applied to finite words.\nFurther\, we show how the size and other structural propert ies of string attractors can be used to obtain new characterizations for i nfinite words.\nMost of the results presented in this talk come from [A co mbinatorial view on string attractors\, Theoret. Comput. Sci. 2021] and [S tring Attractors and Infinite Words\, LATIN 2022] (to appear). URL:https://cow-seminar.github.io/archives/2022.html#20221017-romana END:VEVENT BEGIN:VEVENT UID:20221024-behague@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20221024T130000Z DTEND:20221024T140000Z SUMMARY:Natalie Behague: Synchronizing Times for $k$-sets in Automata DESCRIPTION:An automaton consists of a finite set of states and a collectio n of functions from the set of states to itself. An automaton is synchroni zing if there is a word (that is\, a sequence of functions) that maps all states onto the same state. Černý’s conjecture on the length of the sh ortest such word is one of the most famous open problem in automata theory . We considered the closely related question of determining the minimum le ngth of a word that maps some k states onto a single state.\n\nFor synchro nizing automata\, we found a simple argument for general k almost halving the upper bound on the minimum length of a word sending k states to a sing le state. We further improved the upper bound on the minimum length of a w ord sending 4 states to a singleton from $0.5n^2$ to $≈ 0.459n^2$\, and the minimum length sending 5 states to a singleton from $n^2$ to $≈ 0.79 8n^2$. I will discuss this result and some open questions. URL:https://cow-seminar.github.io/archives/2022.html#20221024-behague END:VEVENT BEGIN:VEVENT UID:20221107-krenn@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20221107T140000Z DTEND:20221107T150000Z SUMMARY:Daniel Krenn: $q$-Recursive Sequences and their Asymptotic Analysis DESCRIPTION:In this talk\, we consider Stern’s diatomic sequence\, the nu mber of\nnon-zero elements in some generalized Pascal's triangle and the n umber\nof unbordered factors in the Thue-Morse sequence as running example s.\nAll these sequences can be defined recursively and lead to the concept \nof so-called $q$-recursive sequences. Here $q$ is an integer and at leas t $2$\,\nand $q$-recursive sequences are sequences which satisfy a specifi c type of\nrecurrence relation: Roughly speaking\, every subsequence whose indices\nrun through a residue class modulo $q^M$ is a linear combination of\nsubsequences where for each of these subsequences\, the indices run\n through a residue class modulo $q^m$ for some $m < M$.\n\nIt turns out tha t this property is quite natural and many combinatorial\nsequences are in fact $q$-recursive. We will see that $q$-recursive\nsequences are related to $q$-regular sequences and a $q$-linear\nrepresentation of a sequence ca n be computed easily. Our main focus is the asymptotic\nbehavior of the su mmatory functions of $q$-recursive sequences. Beside\ngeneral results\, we present a precise asymptotic analysis of our three examples. For the firs t two sequences\, our analysis even leads to\nprecise formulae without err or terms. URL:https://cow-seminar.github.io/archives/2022.html#20221107-krenn END:VEVENT BEGIN:VEVENT UID:20221121-barbieri@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20221121T140000Z DTEND:20221121T150000Z SUMMARY:Sebastián Barbieri: Indistinguishable asymptotic pairs DESCRIPTION:We say two bi-infinite words are asymptotic if they differ in f initely many coordinates. We say they are indistinguishable if for any fin ite word w\, the number of occurrences of w that intersect the set of diff erences in each of them is the same. In this talk we will study these obje cts and show that they are very closely related to Sturmian configurations . We will also show that a higher-dimensional analogue of the theorem hold s\, and as an application of this result we will provide a formula for com puting the complexity of a multidimensional Sturmian configuration on any finite connected support. This is joint work with S. Labbé. URL:https://cow-seminar.github.io/archives/2022.html#20221121-barbieri END:VEVENT BEGIN:VEVENT UID:20221205-rukavicka@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20221205T140000Z DTEND:20221205T150000Z SUMMARY:Josef Rukavicka: Palindromic factorization of rich words DESCRIPTION:A finite word $w$ is called *rich* if it contains $\\vert w\\ve rt+1$ distinct palindromic factors including the empty word. For every fin ite rich word $w$ there are distinct nonempty palindromes $w_1\, w_2\,\\do ts\,w_p$ such that $w=w_pw_{p-1}\\cdots w_1$ and $w_i$ is the longest pali ndromic suffix of $w_pw_{p-1}\\cdots w_i$\, where $1\\leq i\\leq p$. This palindromic factorization is called *UPS-factorization*. Let $luf(w)=p$ be the *length of UPS-factorization* of $w$.\n\nIn 2017\, it was proved that there is a constant $c$ such that if $w$ is a finite rich word and $n=\\v ert w\\vert$ then $luf(w)\\leq c\\frac{n}{\\ln{n}}$.\nWe improve this resu lt as follows: There are constants $\\mu\, \\pi$ such that if $w$ is a fin ite rich word and $n=\\vert w\\vert$ then \\[luf(w)\\leq \\mu\\frac{n}{e^{ \\pi\\sqrt{\\ln{n}}}}\\mbox{.}\\]\nThe constants $c\,\\mu\,\\pi$ depend on the size of the alphabet.\n\n[paper](https://doi.org/10.1016/j.dam.2022.0 3.030) URL:https://cow-seminar.github.io/archives/2022.html#20221205-rukavicka END:VEVENT BEGIN:VEVENT UID:20221219-bell@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20221219T140000Z DTEND:20221219T150000Z SUMMARY:Jason Bell: Noncommutative rational Pólya series DESCRIPTION:A Pólya series over a field $K$ is a formal noncommutative pow er series whose nonzero coefficients are contained in a finitely generated subgroup of the multiplicative group of $K$. A complete description of su ch one-variable series was given by Pólya\, and an extension to general n oncommutative rational series in terms of unambiguous weight automaton was later conjectured by Reutenauer. We explain how to prove Reutenauer’s conjecture and discuss certain decidability aspects of our work. This is joint work with Daniel Smertnig. URL:https://cow-seminar.github.io/archives/2022.html#20221219-bell END:VEVENT BEGIN:VEVENT UID:20230109-fleischmann@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230109T140000Z DTEND:20230109T150000Z SUMMARY:Pamela Fleischmann: $m$-Nearly $k$-Universal Words - Investigating Simon Congruence DESCRIPTION:Determining the index of the Simon congruence is a long outstan ding open problem. Two words $u$ and $v$ are called Simon congruent if the y 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 scatt ered factor of logarithm. Following the idea of scattered factor $k$-unive rsality\, 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 t he universality of repetitions. URL:https://cow-seminar.github.io/archives/2023.html#20230109-fleischmann END:VEVENT BEGIN:VEVENT UID:20230123-dvorakova@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230123T140000Z DTEND:20230123T150000Z SUMMARY:Lubomíra Dvořáková: Essential difference between the repetitive thereshold and asymptotic repetitive threshold of balanced sequences DESCRIPTION:At first\, we will summarize both the history and the state of the art of the critical exponent and the asymptotic critical exponent of b alanced sequences.\nSecond\, we will colour the Fibonacci sequence by suit able constant gap sequences to provide an upper bound on the asymptotic re petitive threshold of $d$-ary balanced sequences. The bound is attained fo r $d$ equal to $2$\, $4$ and $8$ and we conjecture that it happens for inf initely many even $d$'s.\nFinally\, we will reveal an essential differenc e in behavior of the repetitive threshold and the asymptotic repetitive t hreshold of balanced sequences: The repetitive threshold of $d$-ary balan ced sequences is known to be at least $1+1/(d-2)$ for each $d$ larger tha n two. In contrast\, our bound implies that the asymptotic repetitive thre shold of $d$-ary balanced sequences is at most $1+\\phi^3/2^{d-3}$ for eac h $d$ larger than one\, where $\\phi$ is the golden mean.\n\nJoint work wi th Edita Pelantová. URL:https://cow-seminar.github.io/archives/2023.html#20230123-dvorakova END:VEVENT BEGIN:VEVENT UID:20230206-konefal@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230206T140000Z DTEND:20230206T150000Z SUMMARY:Matthew Konefal: Examining the Class of Formal Languages which are Expressible via Word Equations DESCRIPTION:A word equation can be said to express a formal language via ea ch 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. URL:https://cow-seminar.github.io/archives/2023.html#20230206-konefal END:VEVENT BEGIN:VEVENT UID:20230227-duchene@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230227T140000Z DTEND:20230227T150000Z SUMMARY:Aline Parreau and Eric Duchêne: Taking and merging games as rewrit e games DESCRIPTION:(joint work with V. Marsault and M. Rigo)\n\nIn 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 i nformation. Amongst them\, the family of heap games such as the game of Ni m\, subtraction or octal games belong to the the most studied ones. Genera lly\, 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.\n\nIn a second part of the talk\, we will present a generalization of heap games as rewrite games on words. This model was i ntroduced by Waldmann in 2002. Given a finite alphabet and a set of rewrit ing 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 gam e. In this context\, the main question is now about the class of the langu age 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 in vestigate 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. URL:https://cow-seminar.github.io/archives/2023.html#20230227-duchene END:VEVENT BEGIN:VEVENT UID:20230306-steiner@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230306T140000Z DTEND:20230306T150000Z SUMMARY:Léo Poirier and Wolfgang Steiner: Factor-balanced $S$-adic languag es DESCRIPTION: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 th e word\, up to a constant. Similarly\, a language is factor-balanced if th e 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-balance d but not factor-balanced language is given by the Thue-Morse sequence. We establish connections between the two notions\, in particular for languag es given by substitutions and\, more generally\, by sequences of substitut ions. We show that the two notions essentially coincide when the sequence of substitutions is proper. For the example of Thue-Morse-Sturmian languag es\, we give a full characterisation of factor-balancedness. URL:https://cow-seminar.github.io/archives/2023.html#20230306-steiner END:VEVENT BEGIN:VEVENT UID:20230327-starosta@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230327T130000Z DTEND:20230327T140000Z SUMMARY:Štěpán Starosta: On a faithful representation of Sturmian morphi sms DESCRIPTION:The set of morphisms mapping any Sturmian sequence to a Sturmia n sequence forms together with composition the so-called monoid of Sturm. For this monoid\, we define a faithful representation by $(3\\times 3)$-m atrices 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 represen ting a Sturmian morphism if the three cones are invariant under multiplic ation by $R$ or $R^{-1}$. This property offers a new tool to study Sturmia n sequences. We provide\nalternative proofs of four known results on Sturm ian sequences fixed by a primitive morphism and a new result concerning th e square root of a Sturmian sequence. URL:https://cow-seminar.github.io/archives/2023.html#20230327-starosta END:VEVENT BEGIN:VEVENT UID:20230403-shallit@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230403T130000Z DTEND:20230403T140000Z SUMMARY:Jeffrey O. Shallit: New Results in Additive Number Theory via Combi natorics on Words DESCRIPTION:Additive number theory is the study of the additive properties of integers.\nSurprisingly\, we can use techniques from combinatorics on w ords to prove\nresults in this area.\nIn this talk I will discuss the numb er of representations of an integer N as\na sum of elements from some famo us sets\, such as the evil numbers\, the\nodious\nnumbers\, the Rudin-Shap iro numbers\, Wythoff sequences\, etc. URL:https://cow-seminar.github.io/archives/2023.html#20230403-shallit END:VEVENT BEGIN:VEVENT UID:20230508-lapointe@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230508T130000Z DTEND:20230508T140000Z SUMMARY:Mélodie Lapointe: Perfectly clustering words: Induction and morphi sms DESCRIPTION:Perfectly clustering words are special factors in trajectories of discrete interval exchange transformation with symmetric permutation. I f the discrete interval exchange transformation has two intervals\, they a re Christoffel words. Therefore\, perfectly clustering words are a natural generalization of Christoffel words. In this talk\, an induction on discr ete interval exchange transformation with symmetric permutation will be pr esented. 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 c ertain gentle algebras will be presented. URL:https://cow-seminar.github.io/archives/2023.html#20230508-lapointe END:VEVENT BEGIN:VEVENT UID:20230515-kaplan@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230515T130000Z DTEND:20230515T140000Z SUMMARY:Craig Kaplan: An aperiodic monotile DESCRIPTION:A set of shapes is called aperiodic if the shapes admit tilings of\n the plane\, but none that have translational symmetry. A longstandi ng\n open problem asks whether a set consisting of a single shape could\n be aperiodic\; such a shape is known as an aperiodic monotile or\n sometim es an "einstein". The recently discovered "hat" monotile\n settles this p roblem in two dimensions. In this talk I provide\n necessary background o n aperiodicity and related topics in tiling\n theory\, review the history of the search for for an aperiodic\n monotile\, and then discuss the hat a nd its mathematical properties.\n\nFull disclosure: this is the same title and abstract that I just sent to Kevin Hare for the Numeration seminar th e 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. URL:https://cow-seminar.github.io/archives/2023.html#20230515-kaplan END:VEVENT BEGIN:VEVENT UID:20230912-espinoza@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230912T130000Z DTEND:20230912T140000Z SUMMARY:Bastián Espinoza: An $S$-adic characterization of linear-growth co mplexity subshifts DESCRIPTION:In the context of symbolic dynamics\, the class of "linear-grow th complexity subshifts" is of particular relevance as it occurs in a vari ety of areas\, such as geometric dynamical systems\, language theory\, num ber theory\, and numeration systems\, among others. During the intensive s tudy carried out on this subject since the beginning of the 90s\, it was p roposed that a hierarchical decomposition based on $S$-adic sequences that characterizes linear-growth complexity subshifts would be useful to under stand this class. The problem of finding such a characterization was given the name "$S$-adic conjecture" and inspired several influential results i n symbolic dynamics. In this talk\, I will present an $S$-adic characteriz ation of this class as well as some of its applications\, giving in partic ular a solution to this conjecture. URL:https://cow-seminar.github.io/archives/2023.html#20230912-espinoza END:VEVENT BEGIN:VEVENT UID:20230926-currie@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20230926T130000Z DTEND:20230926T140000Z SUMMARY:James Currie: The analogs of overlap-freeness for the period-doubli ng morphism and for the Fibonacci morphism DESCRIPTION:The Thue-Morse morphism is the binary map $\\mu: 0 \\to 01\, 1 \\to 10$. A word $w$ is\noverlap-free if it has no factor of the form $xyx yx$\, where $x$ is\nnon-empty. A deep connection between these two concept s is the engine\nbehind several results:\n\n- The precise characte rization of finite prefixes of infinite\noverlap-free binary words (Fife ’s Theorem)\;\n\n- A precise enumeration of overlap-free binary words\;\n\n- A characterization of all binary patterns encountered by the\nThue-Morse word\;\n\n- The determination of the lexicogra phically least infinite\noverlap-free word.\n\nGiven another morphism\, is there an analog of overlap-freeness which\nfacilitates the proof of simil ar results? We show that the answer is\nyes for the period doubling morphi sm $\\delta :0 \\to 01\, 1\\to 00$\, and for the\nFibonacci morphism $\\va rphi :0\\to 01\, 1\\to 0$. URL:https://cow-seminar.github.io/archives/2023.html#20230926-currie END:VEVENT BEGIN:VEVENT UID:20231010-dvorakova@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20231010T130000Z DTEND:20231010T140000Z SUMMARY:Ľubomíra Dvořáková: String attractors and pseudopalindromic cl osures DESCRIPTION:In this contribution we carry on a study of string attractors o f important classes of sequences.\nAttractors of minimum size of factors/p refixes/particular prefixes of the following sequences have been determine d so far: Sturmian sequences (Mantaci\, Restivo\, Romana\, Rosone\, Sciort ino\, 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á a nd Hendrychová\, 2023).\nRecently\, string attractors in fixed points of k-bonacci-like morphisms have been described (Gheeraert\, Romana\, Stipula nti\, 2023).\n\nIn our talk we aim to present the following results:\nUsin g 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 th e ones found for prefixes by Mantaci et al. It was then straightforward to generalize the result to factors of episturmian sequences.\nObserving use fullness of palindromic closures when dealing with attractors\, we turned our attention to pseudopalindromic prefixes of the so-called binary genera lized pseudostandard sequences. We determined the minimum size attractors in two cases: for pseudostandard sequences obtained when iterating uniquel y the antipalindromic closure (the minimum size is three) and for the comp lementary-symmetric Rote sequences when iterating both palindromic and ant ipalindromic closure (the minimum size is two). URL:https://cow-seminar.github.io/archives/2023.html#20231010-dvorakova END:VEVENT BEGIN:VEVENT UID:20231024-gouletouellet@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20231024T130000Z DTEND:20231024T140000Z SUMMARY:Herman Goulet-Ouellet: Density of rational languages under invarian t measures DESCRIPTION:The notion of density for languages was studied by Schützenber ger in the 60s and by Hansel and Perrin in the 80s. In both cases\, the au thors focused on densities defined by Bernoulli measures. In this talk\, I will present new results about densities of regular languages under invar iant measures of minimal shift spaces. We introduce a compatibility condit ion which implies convergence of the density to a constant which depends o nly on the given rational language. This result can be seen as a form of e quidistribution property. The compatibility condition can be stated either in terms of return words or of a skew product. The passage between the tw o 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. URL:https://cow-seminar.github.io/archives/2023.html#20231024-gouletouellet END:VEVENT BEGIN:VEVENT UID:20231107-puzynina@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20231107T140000Z DTEND:20231107T150000Z SUMMARY:Svetlana Puzynina: Well distributed occurrences property in infinit e words DESCRIPTION: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$\, e ach positive integer $m$\, and each vector $v\\in {\\mathbb Z}_m^d$\, ther e 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 occurrenc es can be used to produce aperiodic pseudorandom number generators with go od statistical behavior. We study the well distributed occurrences propert y for certain families of infinite words including words generated by mor phisms\, Sturmian words and Arnoux–Rauzy words. The talk is based on new and old results. URL:https://cow-seminar.github.io/archives/2023.html#20231107-puzynina END:VEVENT BEGIN:VEVENT UID:20231121-albayrak@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20231121T140000Z DTEND:20231121T150000Z SUMMARY:Seda Albayrak: Quantitative estimates for the size of an intersecti on of sparse automatic sets DESCRIPTION:In 1979\, Erdős conjectured that for $k \\ge 9$\, $2^k$ is\nno t the sum of distinct powers of $3$. That is\, the set of powers of\ntwo ( which is $2$-automatic) and the $3$-automatic set consisting of\nnumbers w hose ternary expansions omit $2$ has finite intersection. A\ntheorem of Co bham (1969) says that if $k$ and $\\ell$ are two\nmultiplicatively indepen dent natural numbers then a subset of the\nnatural numbers that is both $k $- and $\\ell$-automatic is eventually\nperiodic. A multidimensional exte nsion of this theorem was later\ngiven by Semenov (1977). Motivated by Er dős’ conjecture and in\nlight of Cobham’s theorem\, we give a quantit ative version of the\nCobham-Semenov theorem for sparse automatic sets\, s howing that the\nintersection of a sparse $k$-automatic subset of $\\mathb b{N}^d$ and a\nsparse $\\ell$-automatic subset of $\\mathbb{N}^d$ is finit e. Moreover\,\nwe give effectively computable upper bounds on the size of the\nintersection in terms of data from the automata that accept these\nse ts. URL:https://cow-seminar.github.io/archives/2023.html#20231121-albayrak END:VEVENT BEGIN:VEVENT UID:20231205-rosenfeld@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20231205T140000Z DTEND:20231205T150000Z SUMMARY:Matthieu Rosenfeld: Word reconstruction using queries on subwords o r factors DESCRIPTION:I will present some results that we recently obtained about wor d\nreconstruction problems. In this setting you can ask queries from a\nfi xed family of queries about an unknown word $W$ and your goal is to\nrecon struct $W$ by asking the least possible number of queries. We study\nthe q uestion for 3 different families of queries:\n- "How many occurrences of $ u$ in $W$ as a factor?"\, for any $u$\;\n- "How many occurrences of $u$ in $W$ as a subword?"\, for any $u$\;\n- "Does $u$ occur in $W$ as a subword ?"\, for any $u$.\n\nEach of these cases had already been studied\, and we improve the\nbounds for each of them.\nIn particular\, in the second case \, you can ask queries about the\nnumber of occurrences of any given subwo rd. Fleischmann\, Lejeune\,\nManea\, Nowotka and Rigo gave an algorithm th at reconstructs any\nbinary word $W$ of length $n$ in at most $n/2 +1$ que ries. We prove that\n$O((n log n)^{(1/2)})$ queries suffice. In this talk\ , I will provide a few\nnecessary definitions and present our results.\n\n This is joint work with Gwenaël Richomme. URL:https://cow-seminar.github.io/archives/2023.html#20231205-rosenfeld END:VEVENT BEGIN:VEVENT UID:20231219-beaur@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20231219T140000Z DTEND:20231219T150000Z SUMMARY:Pierre Béaur: All I want for Christmas is an algorithm to detect a Sturmian word in an ω-regular language DESCRIPTION:In the enchanting realm of CoWLand\, where computer science wiz ards and mathematics enchanters gather via the magic of the Internet\, a w himsical elf embarks us on a yuletide adventure. Our quest? To detect Stur mian words hidden in the snowy languages of ω-regular automata. As S-adic representations and discrete lines dance around the Christmas tree\, I wi ll present the mischevious magic of desubstitution and its algorithmic app lications.\n\nI start from weak ω-automata\, that is\, labeled graphs tha t accept infinite words\, and characterize when such automata accept a sub stitutive word\, a fixed point\, or a Sturmian word. These methods are ef fective and provide an algorithm relying on S-adic representations. On the way\, we find some other natural applications in combinatorics on words a nd discrete geometry. Then\, I will explain how the methods translate from weak ω-automata to Büchi automata\, what the limits of our techniques a re\, and what are the leads to give this fairytale a proper conclusion. URL:https://cow-seminar.github.io/archives/2023.html#20231219-beaur END:VEVENT BEGIN:VEVENT UID:20240109-mullner@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240109T140000Z DTEND:20240109T150000Z SUMMARY:Clemens Müllner: Synchronizing automatic sequences along Piatetski -Shapiro sequences DESCRIPTION:Automatic sequences - that is\, sequences computable by finite automata - have long been studied from the point of view of combinatorics on words. A notable property of these sequences is that their subword-comp lexity is at most linear. Avgustinovich\, Fon-Der-Flaass and Frid introduc ed the notion of arithmetic subword-complexity - that is the number of dif ferent subwords of length $n$ that appear along some arithmetic progressio n.\nThey also showed that a special class of synchronizing automatic seque nces have at most linear arithmetic subword-complexity and some other clas s of automatic sequences on the alphabet $\\Sigma$ have maximal possible s ubword-complexity $|\\Sigma|^n$.\n\nSynchronizing automatic sequences can be efficiently approximated using periodic functions and are usually more structured than general automatic sequences. We discuss a recent result sh owing that the arithmetic (and even polynomial) subword-complexity of sync hronizing automatic sequences grows subexponentially. This was a key resul t to show that the subword-complexity of synchronizing automatic sequences along regularly growing sequences (such as Piatetski-Shapiro sequences) g rows subexponentially\, which is in stark contrast to other automatic sequ ences such as the Thue-Morse sequence. Moreover\, this was a key ingredien t to obtain rather precise estimates for the arithmetic (and polynomial) s ubword-complexity of general automatic sequences.\n\nThis is joint work wi th Jean-Marc Deshouillers\, Michael Drmota\, Andrei Shubin and Lukas Spieg elhofer. URL:https://cow-seminar.github.io/archives/2024.html#20240109-mullner END:VEVENT BEGIN:VEVENT UID:20240123-konieczny@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240123T140000Z DTEND:20240123T150000Z SUMMARY:Jakub Konieczny: Arithmetical subword complexity of automatic seque nces DESCRIPTION:It is well-known that the subword complexity of an automatic se quence grows at most linearly\, meaning that the number of length-$\\ell$ subwords which appear in a given automatic sequence $a = (a(n))_n$ is at m ost $C \\ell$ for a constant $C$ dependent only on $a$. In contrast\, arit hmetic subword complexity measures the number of subwords which appear alo ng arithmetic progressions\, and can grow exponentially even for very simp le automatic sequences. Indeed\, the classical Thue-Morse sequence has ari thmetic subword complexity $2^{\\ell}$\, which is the maximal possible com plexity for $\\{0\,1\\}$-valued sequence.\n\nTogether with Jakub Byszewski and Clemens Müllner we obtained a decomposition result which allows us t o express any (complex-valued) automatic sequence as the sum of a structur ed part\, which is easy to work with\, and a part which is pseudorandom or uniform from the point of view of higher order Fourier analysis. We now a pply these techniques to the study of arithmetic subword complexity of aut omatic sequences. We show that for each automatic sequence $a$ there exist s a parameter $r$ --- which we dub "effective alphabet size" --- such that the arithmetic subword complexity of $a$ is at least $r^{\\ell}$ and at m ost $(r+o(1))^{\\ell}$.\n\nThis talk is based on joint work with Jakub Bys zewski and Clemens Müllner\, and is closely related to the previous talk of Clemens Müllner at One World Combinatorics on Words Seminar. URL:https://cow-seminar.github.io/archives/2024.html#20240123-konieczny END:VEVENT BEGIN:VEVENT UID:20240206-rowland@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240206T140000Z DTEND:20240206T150000Z SUMMARY:Eric Rowland: Algebraic power series and their automatic complexity DESCRIPTION:A theorem of Christol gives a characterization of automatic seq uences over a finite field: a sequence is automatic if and only if its gen erating series is algebraic. Since there are two representations for such a sequence -- as an automaton and as a bivariate polynomial -- a natural q uestion is how the size of one representation relates to the size of the o ther. Bridy used tools from algebraic geometry to bound the size of the mi nimal automaton in terms of the size of the minimal polynomial. We have a new proof of Bridy's bound that works by converting algebraic sequences to diagonals of rational functions. Crucially for our interests\, this appro ach can be adapted to work not just over a finite field but over the integ ers modulo a prime power. This is joint work with Manon Stipulanti and Ree m Yassawi. URL:https://cow-seminar.github.io/archives/2024.html#20240206-rowland END:VEVENT BEGIN:VEVENT UID:20240220-cabezas@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240220T140000Z DTEND:20240220T150000Z SUMMARY:Christopher Cabezas: Large normalizer of odometers and higher-dimen sional automatic sequences DESCRIPTION:For a $\\mathbb Z^d$ topological dynamical system $(X\, T\, \\m athbb Z^d)$\, an isomorphism is a self-homeomorphism $\\phi : X\\to X$ suc h that for some matrix $M \\in GL(d\, \\mathbb Z)$ and any $n \\in \\mathb b Z^d$\, $\\phi \\circ T^n = T^{M_n} \\circ \\phi$\, where $T^n$ denote th e self-homeomorphism of $X$ given by the action of $n \\in \\mathbb Z^d$. The collection of all the isomorphisms forms a group that is the normalize r of the set of transformations $T^n$. In the one-dimensional case isomorp hisms correspond to the notion of flip conjugacy of dynamical systems and by this fact are also called reversing symmetries.\n\nThese isomorphisms a re not well understood even for classical systems. In this talk we will pr esent a description of them for odometers and more precisely for $\\mathbb Z^2$-constant base odometers\, that is not simple. We deduce a complete d escription of the isomorphism of some $\\mathbb Z^2$ minimal substitution subshifts. Thanks to this\, we will give the first known example of a mini mal zero-entropy subshift with the largest possible normalizer group.\nThi s is a joint work with Samuel Petite (Universitè de Picardie Jules Verne) . URL:https://cow-seminar.github.io/archives/2024.html#20240220-cabezas END:VEVENT BEGIN:VEVENT UID:20240305-lidbetter@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240305T140000Z DTEND:20240305T150000Z SUMMARY:Finn Lidbetter: Improved bound for the Gerver-Ramsey collinearity p roblem DESCRIPTION:Let $S$ be a finite subset of $\\mathbb{Z}^n$. A vector\nsequen ce $(z_i)$ is an $S$-walk if and only if $z_{i+1}-z_i$ is an\nelement of $ S$ for all $i$. Gerver and Ramsey showed in 1979 that for\n$S\\subset\\mat hbb{Z}^3$ there exists an infinite $S$-walk in which no\n$5^{11}+1=48\,828 \,126$ points are collinear. Using the same general\napproach\, but with t he aid of a computer search\, we show how to\nimprove the bound to $189$. We begin by restating the infinite\n$S$-walk as the fixed point of iterati ng a morphism defined for a $12$\nletter alphabet. URL:https://cow-seminar.github.io/archives/2024.html#20240305-lidbetter END:VEVENT BEGIN:VEVENT UID:20240319-kraaikamp@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240319T140000Z DTEND:20240319T150000Z SUMMARY:Cor Kraaikamp: An introduction to $N$-expansions with a finite set of digits DESCRIPTION:In this talk $N$-expansions\, and in particular $N$-expansions with a finite set\nof digits\, will be introduced. Although $N$-expansions were introduced as\nrecent as 2008 by Ed Burger and some of his students\ , quite a number of\npapers have appeared on these variations of the regul ar continued fraction\nexpansion. By choosing a domain for the underlying Gauss-map which does\nnot contain the origin\, a continued fraction with f initely many digits was\nintroduced by Niels Langeveld in his MSc-thesis. It turns out that these\ncontinued fraction algorithms exhibit a very comp licated and surprising rich\ndynamical behavior.\n\nThis talk is based on joint work with Yufei Chen (Shanghai\, Delft)\, Jaap\nde Jonge (UvA\, Amst erdam)\, Karma Dajani (Utrecht)\, Niels Langeveld\n(Montan U.\, Leoben)\, Hitoshi Nakada (Keio\, Yokohama)\, and Niels van der\nWekken (Netcompany). URL:https://cow-seminar.github.io/archives/2024.html#20240319-kraaikamp END:VEVENT BEGIN:VEVENT UID:20240402-campbell@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240402T130000Z DTEND:20240402T140000Z SUMMARY:John Campbell: On the evaluation of infinite products involving aut omatic sequences DESCRIPTION:We explore and discuss some recently introduced techniques conc erning the evaluation of infinite products involving automatic sequences. URL:https://cow-seminar.github.io/archives/2024.html#20240402-campbell END:VEVENT BEGIN:VEVENT UID:20240416-piorkowski@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240416T130000Z DTEND:20240416T140000Z SUMMARY:Radosław Piórkowski: Universal quantification in automatic struct ures—an ExpSpace-hard nut to crack DESCRIPTION:Automatic structures are structures whose universe and relation s can be represented as regular languages. It follows from the standard cl osure properties of regular languages that the first-order theory of an au tomatic structure is decidable.\n\nWhile existential quantifiers can be el iminated in linear time by application of a homomorphism\, universal quant ifiers are commonly eliminated via the identity ∀x. Φ ≡ ¬(∃x. ¬Φ ). If Φ is represented in the standard way as an NFA\, a priori this appr oach results in a doubly exponential blow-up. However\, the recent literat ure has shown that there are classes of automatic structures for which uni versal quantifiers can be eliminated without this blow-up when treated as first-class citizens and not resorting to double complementation. The exis ting lower bounds for some classes of automatic structures show that a sin gly exponential blow-up is unavoidable when eliminating a universal quanti fier\, but it is not known whether there may be better approaches that avo id the naïve doubly exponential blow-up.\nWe answer this question negativ ely.\n\nIn my talk\, following a short introduction to the field of automa tic structures\, I will present the construction of a family of NFA repres enting automatic relations for which the minimal NFA recognising the langu age after a universal projection step is doubly exponential\, and deciding whether this language is empty is ExpSpace-complete.\n\nBased on the pape r: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023. 13\n\nAuthors: Christoph Haase\, R.P.\n\nKeywords: automatic structures\, universal projection\, tiling problems\, state complexity. URL:https://cow-seminar.github.io/archives/2024.html#20240416-piorkowski END:VEVENT BEGIN:VEVENT UID:20240430-baake@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240430T130000Z DTEND:20240430T140000Z SUMMARY:Michael Baake: Hats\, CAPs and Spectres DESCRIPTION:The recently discovered Hat is an aperiodic\nmonotile for the E uclidean plane\, which needs a reflected\nversion for this property. The S pectre does not have this\n(tiny) deficiency. We discuss the topological a nd dynamical\nproperties of the Hat tiling\, how the CAP relates to it\, a nd\nwhat the long-range order of both tilings is. Finally\, we\nbriefly de scribe the analogous structure for the Spectre tiling. URL:https://cow-seminar.github.io/archives/2024.html#20240430-baake END:VEVENT BEGIN:VEVENT UID:20240514-rukavicka@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240514T130000Z DTEND:20240514T140000Z SUMMARY:Josef Rukavicka: Restivo Salemi property for $\\alpha$-power free l anguages with $\\alpha \\geq 5$ and $k \\geq 3$ letters DESCRIPTION:In 2009\, Shur published the following conjecture: Let $L$ be a power-free language and let $e(L)\\subseteq L$ be the set of words of $L$ that can be extended to a bi-infinite word respecting the given power-fre eness. If $u\,v \\in e(L)$ then $uwv \\in e(L)$ for some word $w$. Let $L_ {k\,\\alpha}$ denote an $\\alpha$-power free language over an alphabet wit h $k$ letters\, where $\\alpha$ is a positive rational number and $k$ is p ositive integer. We prove the conjecture for the languages $L_{k\,\\alpha} $\, where $\\alpha\\geq 5$ and $k \\geq 3$.\n\nhttps://arxiv.org/abs/2312. 10061 URL:https://cow-seminar.github.io/archives/2024.html#20240514-rukavicka END:VEVENT BEGIN:VEVENT UID:20240528-ochem@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240528T130000Z DTEND:20240528T140000Z SUMMARY:Pascal Ochem: Characterization of morphic words. DESCRIPTION:The famous Hall-Thue word\, fixed point of the morphism\n0 -> 0 12\, 1 -> 02\, 2 -> 1\, is essentially the only infinite\nternary word avo iding squares and the words 010 and 212.\n\nI will present many examples o f this phenomenon\, that is\,\nwhen every recurrent word satisfying some a voidance constraints\nhas the same factor set as a morphic word.\n\nThis i s a joint work with Golnaz Badkobeh\, Matthieu Rosenfeld\,\nL'ubomíra Dvo řáková\, Daniela Opočenská\, Aseem Baranwal\,\nJames Currie\, Lucas M ol\, Narad Rampersad\, and Jeffrey Shallit. URL:https://cow-seminar.github.io/archives/2024.html#20240528-ochem END:VEVENT BEGIN:VEVENT UID:20240611-whiteland@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240611T130000Z DTEND:20240611T140000Z SUMMARY:Markus Whiteland: What I know about Parikh-collinear morphisms DESCRIPTION:A morphism is Parikh-collinear if its adjacency matrix has rank at most one. For example\, the famous Thue-Morse morphism is such morphis m. Some of their properties have been considered in the literature\, e.g.\ , by Allouche et al. [Comb. Theory 1\, 2021] (in passing) and Cassaigne et al. [Int. J. Found. Comput. 22\, 2011]\; the latter characterises Parikh- collinear morphisms as those morphisms that map any infinite word (over th e domain alphabet) to a word with bounded abelian complexity.\n\nIn this t alk I will focus on properties of Parikh-collinear morphisms and their fix ed points from the viewpoint of binomial complexities. We will also consid er automatic (in the sense of Allouche and Shallit) aspects related to suc h fixed points.\n\nThe talk is based on joint work with M. Rigo and M. Sti pulanti. URL:https://cow-seminar.github.io/archives/2024.html#20240611-whiteland END:VEVENT BEGIN:VEVENT UID:20240625-cassaigne@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240625T130000Z DTEND:20240625T140000Z SUMMARY:Julien Cassaigne: The Heinis Spectrum DESCRIPTION:Many families of infinite words (or of subshifts) have a subwor d complexity\nfunction $p(n)$ that grows linearly. It has sometimes a ver y simple form\n(such as $n + 1$\, $2n + 1$\, etc.)\, but often a more comp licated behaviour\,\nas for the Thue-Morse word. In his Ph.D. thesis\, Al ex Heinis introduced the\nset $\\Omega$ of pairs $(\\alpha\,\\beta)$ such that $\\alpha = \\liminf p(n)/n$\nand $\\beta = \\limsup p(n)/n$ for some infinite word. For instance\, the\nThue-Morse word gives the point $(3\, 10/3)$. But not every point with\n$\\alpha \\leq \\beta$ can be obtained\ , and it is a challenge to characterize\npoints in $\\Omega$. We present some properties of this set\, and some\nquestions that we find interesting . URL:https://cow-seminar.github.io/archives/2024.html#20240625-cassaigne END:VEVENT BEGIN:VEVENT UID:20240709-simpson@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240709T130000Z DTEND:20240709T140000Z SUMMARY:Jamie Simpson: Palindromic Periodicities DESCRIPTION:If $p$ and $s$ are palindromes then a factor of the infinite wo rd $(ps)^\\omega$ which has length at least $|ps|$ is called a palindromic periodicity. In this talk I will first describe some simple properties o f these objects and then show how they can appear. For example a word whi ch is both periodic and a palindrome is a palindromic periodicity. Next I' ll present a periodicity lemma similar to the Fine Wilf Lemma but applied to palindromic periodicities. The talk will finish with some suggestions for further research. URL:https://cow-seminar.github.io/archives/2024.html#20240709-simpson END:VEVENT BEGIN:VEVENT UID:20240910-yao@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240910T130000Z DTEND:20240910T140000Z SUMMARY:Jia-Yan Yao: When is an automatic number transparent? DESCRIPTION:In this talk we introduce a new notion to\nmeasure the complexi ty of automatic numbers\,\nwhich are either rational or transcendental.\nW e study basic properties of this notion\, and\n exhibit an algorithm to co mpute it. In particular\,\nwe shall characterize all the automatic numbers \nwhich are transparent. As applications\, we shall\nalso compute the com plexity of some well-known\nautomatic numbers. URL:https://cow-seminar.github.io/archives/2024.html#20240910-yao END:VEVENT BEGIN:VEVENT UID:20240924-schaeffer@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20240924T130000Z DTEND:20240924T140000Z SUMMARY:Luke Schaeffer: Summation and transduction of automatic sequences DESCRIPTION:We examine the theory of computing partial sums or transduction s in automatic sequences\, including a theorem of Dekking and its generali zation. We give a number of examples involving paperfolding words and Stur mian sequences. URL:https://cow-seminar.github.io/archives/2024.html#20240924-schaeffer END:VEVENT BEGIN:VEVENT UID:20241008-golafshan@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20241008T130000Z DTEND:20241008T140000Z SUMMARY:Mehdi Golafshan: Factor complexity of the most significant digits a nd unipotent dynamics on a torus DESCRIPTION:In this talk\, we explore the dynamics of unipotent flows on a torus and how these techniques lead to interesting applications in number theory. Specifically\, I'll focus on the following problem: let \\(d\\) be a positive integer\, and \\(a > 0\\) be a real number. Consider a square- free integer \\(b \\geqslant 5\\) such that \\(a\\) and \\(b\\) are multip licatively independent. We then examine the sequence \\((\\mathbf{w}_n)\\) \, where \\(\\mathbf{w}_n\\) represents the most significant digit of \\(a ^{n^d}\\) when written in base \\(b\\). I will present our result\, showin g that the complexity function of this sequence\, with only a finite numbe r of exceptions\, is a polynomial function. This work connects dynamics on homogeneous spaces with problems in symbolic dynamics and number theory\, offering new insights into sequence complexity.\n\nBased on a joint work with Ivan Mitrofanov: https://arxiv.org/abs/2402.16210 URL:https://cow-seminar.github.io/archives/2024.html#20241008-golafshan END:VEVENT BEGIN:VEVENT UID:20241022-carton@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20241022T130000Z DTEND:20241022T140000Z SUMMARY:Olivier Carton: Mahler equations for Zeckendorf numeration DESCRIPTION:Let $U = (u_n)$ be a Pisot numeration system. A sequence $(f_n )$ taking values\nover a commutative ring $R$\, possibly infinite\, is sai d to be *$U$-regular*\nif there exists a *weighted* automaton which output s $f_n$ when it reads\n$(n)_U$. For base-$q$ numeration\, with $q ∈ ℕ $\, $q$-regular sequences\nwere introduced and studied by Allouche and Sha llit\, and they are a\ngeneralisation of $q$-automatic sequences $(f_n)$\, where $f_n$ is the output of a\ndeterministic automaton when it reads $(n )_q$. Becker\, and also Dumas\, made\nthe connection between $q$-regular sequences\, and *$q$-Mahler type*\nequations. In particular a $q$-regular sequence gives a solution to an\nequation of $q$-Mahler type\, and convers ely\, the solution of an\n*isolating*\, or Becker\, equation of $q$-Mahler type is $q$-regular.\n\nWe define generalised equations of $Z$-Mahler typ e\, based on the Zeckendorf\nnumeration system $Z$. We show that if a sequ ence over a commutative ring is\n$Z$-regular\, then it is the sequence of coefficients of a series which is a\nsolution of a $Z$-Mahler equation. Co nversely\, if the $Z$-Mahler equation is\nisolating\, then its solutions d efine $Z$-regular sequences. We provide an\nexample to show that there ex ist non-isolating $Z$-Mahler equations whose\nsolutions do not define $Z$- regular sequences. Our proof yields a new\nconstruction of weighted automa ta that generate classical $q$-regular\nsequences.\n\nThis is joint work w ith Reem Yassawi. URL:https://cow-seminar.github.io/archives/2024.html#20241022-carton END:VEVENT BEGIN:VEVENT UID:20241105-menibus@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20241105T140000Z DTEND:20241105T150000Z SUMMARY:Benjamin Hellouin de Menibus: String attractors for infinite words DESCRIPTION:A string attractor of a word w is a set of marked positions suc h that every factor of w has an occurrence that crosses one of the marked positions. This is a recent concept whose motivation comes from the study of compression algorithms\, but that was studied very soon after for its c ombinatorial properties. In particular\, the size or span of the smallest string attractor for a word can be seen as a measure of its complexity\, a nd this point of view led to studying smallest string attractors for famil ies of classical words\, such as the prefixes of the Fibonacci word.\n\nWh ile it is fruitful to study smallest string attractors on finite prefixes or factors of infinite words\, we can also define string attractors direct ly on infinite words. Unfortunately\, there is no good notion of smallest string attractor in this setting\, except when there is a finite one\, whi ch in the one-sided case means that the word is periodic.\n\nFortunately\, the two-sided case is more rich in this regard\, and is the topic of this talk. We study and completely characterise two-sided infinite words that admit a finite string attractor\, and relate the size of the smallest attr actor to their complexity function. We also get another characterisation o f (quasi-)Sturmian words. I will also mention some side results regarding periodic string attractors and / or string attractors for shifts.\n\nThis is a joint work with Pierre Béaur and France Gheeraert. URL:https://cow-seminar.github.io/archives/2024.html#20241105-menibus END:VEVENT BEGIN:VEVENT UID:20241119-vivion@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20241119T140000Z DTEND:20241119T150000Z SUMMARY:Léo Vivion: Balancedness constants of words generated by billiards in the hypercube DESCRIPTION:A hypercubic billiard word in dimension $d$ is an infinite $d$- ary word encoding the faces successively hit by a billiard ball moving in the unit cub of $\\mathbb{R}^d$\, in which two parallel faces are labeled by the same letter. Square billiard words generated by a (billiard ball wi th an initial) momentum with rationally independent coordinates are Sturmi an\, so hypercubic billiard words generated by a momentum with rationally independent coordinates are one dynamical generalization of Sturmian words . Hence\, it is natural to ask which properties satisfied by Sturmian word s are still satisfied by hypercubic billiard words.\n\nWhile the subword c omplexity of hypercubic billiard words has been extensively studied at the end of the 1990s and the beginning of the 2000s (Arnoux\, Mauduit\, Shiok awa and Tamura 1994\, Baryshnikov 1995 and Bédaride 2003-2009)\, their ab elian properties have been much less studied: only Vuillon (2003) initiate d the study of their balancedness.\n\nIn this talk\, I will first recall t he results obtained by Vuillon\, and then\, give a complete characterizati on of the imbalance of hypercubic billiard words generated by a momentum w ith rationally independent coordinates. In a second part\, I will also dis cuss the case of momenta with rationally dependent coordinates. URL:https://cow-seminar.github.io/archives/2024.html#20241119-vivion END:VEVENT BEGIN:VEVENT UID:20241217-nakashima@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20241217T140000Z DTEND:20241217T150000Z SUMMARY:Yuto Nakashima: On the Number of Non-equivalent Parameterized Squar es in a String DESCRIPTION:A string $s$ is called a parameterized square when $s = xy$ for strings $x$\, $y$ and $x$ and $y$ are parameterized equivalent.\nKociumak a et al. showed the number of parameterized squares\, which are non-equiva lent in parameterized equivalence\, in a string of length $n$ that contain s $\\sigma$ distinct characters is at most $2 \\sigma! n$ [TCS 2016].\nRec ently\, we showed that the maximum number of non-equivalent parameterized squares is less than $\\sigma n$\, which significantly improves the best-k nown upper bound by Kociumaka et al.\n\nThis is a joint work with Rikuya H amai\, Kazushi Taketsugu\, Shunsuke Inenaga\, and Hideo Bannai (presented at SPIRE 2024). URL:https://cow-seminar.github.io/archives/2024.html#20241217-nakashima END:VEVENT BEGIN:VEVENT UID:20250114-reutenauer@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250114T140000Z DTEND:20250114T150000Z SUMMARY:Christophe Reutenauer: Christoffel matrices and Sturmian determinan ts DESCRIPTION:Work in collaboration with Jeffrey Shallit.\n\n1. The set of Ch ristoffel matrices (that is\, Burrows-Wheeler matrices of Christoffel word s) of size $n$ by $n$\, where the alphabet is some commutative ring $R$\, form a monoid under multiplication\, and those which are invertible\, form a subgroup of $GL_n(R)$.\n(this result was also obtained independently by Luca Zamboni)\n\n2. The determinant of a Christoffel matrix has a simple form\, using the Zolotareff symbol (the latter extends the Jacobi symbol). \n\n3. Taking $n$ factors of length $n$ of a Sturmian sequence over $0$\, $1$\, one obtains a matrix and a determinant. There are$n+1$ such determi nants\; ordering them suitably\, these $n+1$ determinants form a word on a two- or three-letter alphabet contained in $Z$\; this word is perfectly c lustering. If there are three letters\, then one of them is the sum of the two others. URL:https://cow-seminar.github.io/archives/2025.html#20250114-reutenauer END:VEVENT BEGIN:VEVENT UID:20250128-mol@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250128T140000Z DTEND:20250128T150000Z SUMMARY:Lucas Mol: Avoiding abelian and additive powers in rich words DESCRIPTION:We construct an infinite additive 5-power-free rich word over $ \\{0\,1\\}$ and an infinite additive 4-power-free rich word over $\\{0\,1\ ,2\\}$. Both constructions involve affine morphisms\, for which the lengt h and sum of the images of the letters are linear functions of the letters . This allows us to prove the additive power-freeness of our construction s using a recent variation of the template method due to Currie\, Mol\, Ra mpersad\, and Shallit. URL:https://cow-seminar.github.io/archives/2025.html#20250128-mol END:VEVENT BEGIN:VEVENT UID:20250211-rukavicka@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250211T140000Z DTEND:20250211T150000Z SUMMARY:Josef Rukavicka: Palindromic length of infinite aperiodic words DESCRIPTION:The palindromic length of the finite word $v$ is equal to the m inimal number of palindromes whose concatenation is equal to $v$. It was c onjectured in 2013 that for every infinite aperiodic word $x$\, the palind romic length of its factors is not bounded.\nWe prove this conjecture to b e true.\n\nHere is [the paper](https://arxiv.org/abs/2410.12714). URL:https://cow-seminar.github.io/archives/2025.html#20250211-rukavicka END:VEVENT BEGIN:VEVENT UID:20250225-pawlik@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250225T140000Z DTEND:20250225T150000Z SUMMARY:Bartek Pawlik: Words Avoiding Tangrams DESCRIPTION:Work in collaboration with Michał Dębski\, Jarosław Grytczuk \, Jakub Przybyło and Małgorzata Śleszyńska-Nowak.\n\nIf\, in a given word $W$\, each letter appears an even number of times\, then $W$ can be s plit into two identical\, disjoint subwords. For example\, the word $\\mat htt{hotshots}$ can be split into two $\\mathtt{hots}$ by dividing the word exactly in the middle: $\\mathtt{hots\\\,|\\\,hots}$. More generally\, an y square can be separated into two identical words with a single cut. The word $\\mathtt{tattletale}$ requires three cuts: $\\mathtt{tat\\\,|\\\,tle \\\,|\\\,ta\\\,|\\\,le}$ to split it into two words $\\mathtt{tatle}$. The minimal number of cuts needed to divide a word $W$ into two identical sub words is called the *cut number* of $W$. During the lecture\, I will discu ss several topics related to the cut number. URL:https://cow-seminar.github.io/archives/2025.html#20250225-pawlik END:VEVENT BEGIN:VEVENT UID:20250311-letouzey@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250311T140000Z DTEND:20250311T150000Z SUMMARY:Pierre Letouzey: Generalizing some Hofstadter functions: G\, H and beyond DESCRIPTION:Hofstadter's G function is recursively defined via $G(0)=0$ and then\n$G(n)=n-G(G(n-1))$. Following Hofstadter\, a family $(F_k)$ of simi lar\nfunctions is obtained by varying the number $k$ of nested recursive c alls\nin this equation. We present here a few nice properties of these fun ctions.\nIn particular\, they can be described via some infinite morphic w ords\ngeneralizing the Fibonacci word. This was crucial for proving that\n this family is ordered pointwise: for all $k$ and $n$\, $F_k(n) \\le F_{k+ 1}(n)$.\nMoreover\, these functions have a simple behavior on well-chosen numerical\nrepresentations (Zeckendorf decompositions for some Fibonacci-l ike sequences).\nThanks to that\, we were also able to estimate the discre pancies for these $F_k$\,\ni.e. the maximal distances between each $F_k$ a nd its linear equivalent.\nThis whole work was formally proved using the C oq proof assistant\n(except for a beautiful fractal !) and we will give a gentle introduction\nto this Coq development.\n\nJoint work with Shuo Li ( U. Winnipeg) and Wolfgang Steiner (IRIF\, Paris). URL:https://cow-seminar.github.io/archives/2025.html#20250311-letouzey END:VEVENT BEGIN:VEVENT UID:20250325-bui@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250325T140000Z DTEND:20250325T150000Z SUMMARY:Vuong Bui: An explicit condition for boundedly supermultiplicative subshifts DESCRIPTION:We study some properties of the growth rate of $L(A\,F)$\, tha t is\, the language of words over the alphabet $A$ avoiding the set of for bidden factors $F$. We first provide a sufficient condition on $F$ and $A$ for the growth of $L(A\,F)$ to be boundedly supermultiplicative. That is \, there exist constants $C>0$ and $\\alpha\\ge 0$\, such that for all $n$ \, the number of words of length $n$ in $L(A\,F)$ is between $\\alpha^n$ a nd $C\\alpha^n$. In some settings\, our condition provides a way to comput e $C$\, which implies that $\\alpha$\, the growth rate of the language\, i s also computable whenever our condition holds.\nWe also apply our techniq ue to the specific setting of power-free words where the argument can be s lightly refined to provide better bounds. Finally\, we apply a similar ide a to $F$-free circular words and in particular we make progress toward a c onjecture of Shur about the number of square-free circular words. URL:https://cow-seminar.github.io/archives/2025.html#20250325-bui END:VEVENT BEGIN:VEVENT UID:20250408-kaneko@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250408T130000Z DTEND:20250408T140000Z SUMMARY:Hajime Kaneko: Analogs of Markoff and Lagrange spectra on one-sided shift spaces DESCRIPTION:The Lagrange spectrum is related to the rational approximations of badly\napproximable numbers. The discrete part of the spectrum is deno ted in terms\nof Christoffel words. A multiplicative analog of the Lagrang e spectrum was\nrecently investigated\, which is defined by Diophantine ap proximations of geometric sequences and more general linear recurrences. D ubickas investigated\nthe minimal limit points of certain multiplicative M arkoff-Lagrange spectra in\nterms of symbolic dynamical systems and certai n substitutions.\n\nIn this talk\, we study an analog of the Markoff-Lagra nge spectrum for general\none-sided shift spaces. As our main results\, we determine the discrete parts and\nminimal limit points in terms of $S$-ad ic sequences\, where $S$ is an infinite set of\nsubstitutions. This is joi nt work with Wolfgang Steiner. URL:https://cow-seminar.github.io/archives/2025.html#20250408-kaneko END:VEVENT BEGIN:VEVENT UID:20250422-greenfeld@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250422T130000Z DTEND:20250422T140000Z SUMMARY:Be'eri Greenfeld: On the Complexity of Infinite Words DESCRIPTION:Given an infinite word $w$\, its complexity function $p_w(n)$ c ounts the number of distinct subwords of length $n$ it contains. A longsta nding open problem in the combinatorics of infinite words is the {\\it inv erse problem}: describe which functions $f: \\mathbb N \\to \\mathbb N$ ar ise as complexity functions of infinite words. Such functions must be non- decreasing and\, unless eventually constant\, strictly increasing\; they m ust also be submultiplicative\, i.e.\, $f(n+m)≤f(n)f(m)$. Many interesti ng results\, both positive and negative\, have been obtained in this direc tion.\n\nWe resolve this problem up to asymptotic equivalence in the sense of large-scale geometry. Specifically\, given any increasing\, submultipl icative function $f$\, we construct an infinite recurrent word $w$ such th at $c f(cn) ≤ p_w(n) ≤ d f(dn)$ for some constants $c\,d>0$. For unifo rmly recurrent words\, we obtain a weaker version allowing a linear error factor. Time permitting\, we will discuss connections and applications of these results to asymptotic questions in algebra.\n\nJoint work with C. G. Moreira and E. Zelmanov. URL:https://cow-seminar.github.io/archives/2025.html#20250422-greenfeld END:VEVENT BEGIN:VEVENT UID:20250506-peltomaki@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250506T130000Z DTEND:20250506T140000Z SUMMARY:Jarkko Peltomäki: The repetition threshold for ternary rich words DESCRIPTION:In the recent years\, it has been popular to determine the leas t critical exponent in specific families of infinite words. In this talk\, I will explain what is known about the least critical exponents for infin ite words that are rich in palindromes. In particular\, I will outline the proof of our result that the least critical exponent for ternary rich inf inite words equals $1 + 1/(3 - \\mu) \\approx 2.25876324$\, where $\\mu$ i s the unique real root of the polynomial $x^3 - 2x^2 - 1$. This result is based on proving a structure theorem for ternary rich infinite words that avoid $16/7$-powers. In addition\, I discuss some recent progress on deter mining the least asymptotic critical exponents for rich infinite words.\n\ nJoint work with L. Mol and J. D. Currie. URL:https://cow-seminar.github.io/archives/2025.html#20250506-peltomaki END:VEVENT BEGIN:VEVENT UID:20250520-jain@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250520T130000Z DTEND:20250520T140000Z SUMMARY:Pranjal Jain: Partial Sums of Binary Subword-Counting Sequences DESCRIPTION:Let $w$ be a finite word over the alphabet $\\{0\,1\\}$. For an y natural number $n$\, let $s_w(n)$ denote the number of occurrences of $w $ in the binary expansion of $n$ as a scattered subsequence. The talk aims to provide a systematic way of studying the growth of the partial sum $\\ sum_{n=0}^N (-1)^{s_w(n)}$ as $N \\to \\infty$. In particular\, these tech niques yield several classes of words $w$ with $\\sum_{n=0}^N (-1)^{s_w(n) } = O(N^{1-\\epsilon})$ for some $\\epsilon >0$. We begin by motivating th e ideas using the case of $w=01\,011$. The talk is based on joint work wit h Shuo Li. URL:https://cow-seminar.github.io/archives/2025.html#20250520-jain END:VEVENT BEGIN:VEVENT UID:20250603-bright@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250603T130000Z DTEND:20250603T140000Z SUMMARY:Curtis Bright: Mathematical Problems with SATisfying Solutions DESCRIPTION:Automated reasoning tools have been effectively used to solve a variety of problems in discrete mathematics. In this talk\, I will intro duce satisfiability (SAT) solvers and highlight a variety of problems in d iscrete mathematics that have been tackled with a SAT solver. As a case s tudy\, I will demonstrate how a SAT solver can be used to make progress on a question arising in combinatorics on words involving North-East lattice paths. URL:https://cow-seminar.github.io/archives/2025.html#20250603-bright END:VEVENT BEGIN:VEVENT UID:20250617-aranov@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250617T130000Z DTEND:20250617T140000Z SUMMARY:Noy Soffer Aranov: Escape of Mass of Sequences DESCRIPTION:One way to study the distribution of nested quadratic number fi elds satisfying fixed arithmetic relationships is through the evolution of continued fraction expansions. In the function field setting\, it was sho wn by de Mathan and Teullie that given a quadratic irrational $\\Theta$\, the degrees of the periodic part of the continued fraction of $t^n\\Theta$ are unbounded. Paulin and Shapira improved this by proving that quadratic irrationals exhibit partial escape of mass. Moreover\, they conjectured t hat they must exhibit full escape of mass. We construct counterexamples to their conjecture in every characteristic. In this talk we shall discuss t he technique of proof as well as the connection between escape of mass in continued fractions\, Hecke trees\, and number walls. This is part of join t works with Erez Nesharim and Uri Shapira and with Steven Robertson. URL:https://cow-seminar.github.io/archives/2025.html#20250617-aranov END:VEVENT BEGIN:VEVENT UID:20250715-krawczyk@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250715T130000Z DTEND:20250715T140000Z SUMMARY:Elżbieta Krawczyk: Quasi-fixed points of substitutions and substit utive systems DESCRIPTION:We study automatic sequences and automatic systems (symbolic dy namical systems) generated by general constant length (nonprimitive) subst itutions. While an automatic system is typically uncountable\, the set of automatic sequences is countable\, implying that most sequences within an automatic system are not themselves automatic. We provide a complete class ification of automatic sequences that lie in a given automatic system in t erms of the so-called quasi-fixed points of the substitution defining the system. Quasi-fixed points have already appeared implicitly in a few place s (e.g. in the study of substitutivity of lexicographically minimal point s in substitutive systems or in the study of subsystems of substitutive sy stems) and they have been described in detail by Shallit and Wang and\, mo re recently\, Béal\, Perrin\, and Restivo . We conjecture that a similar statement holds for general nonconstant length substitutions. URL:https://cow-seminar.github.io/archives/2025.html#20250715-krawczyk END:VEVENT BEGIN:VEVENT UID:20250902-joshi@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250902T130000Z DTEND:20250902T140000Z SUMMARY:Gandhar Joshi: Monochromatic Arithmetic Progressions in Sturmian se quences DESCRIPTION:This is joint work with Dan Rust. We define Monochromatic arith metic progression (MAP) as the repetition of a symbol (traditionally colou r) with a constant difference in a sequence. We study thresholds of the le ngths of MAPs in the Fibonacci word in our paper https://doi.org/10.1016/j .tcs.2025.115391\, which not only resolves a few problems left open by pre vious works revolving around MAPs in symbolic sequences but also reveals a straightforward method to find a formula that finds longest lengths of MA Ps for all Sturmians. This extension is dealt with in the author's PhD the sis. URL:https://cow-seminar.github.io/archives/2025.html#20250902-joshi END:VEVENT BEGIN:VEVENT UID:20250916-kishi@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20250916T130000Z DTEND:20250916T140000Z SUMMARY:Kaisei Kishi: Net Occurrences in Fibonacci and Thue-Morse Words DESCRIPTION:In a string $T$\, an occurrence of a substring $S=T[i ... j]$ i s a net occurrence if $S$ is repeated in $T$\, while both left extension $ T[i-1\, ... j]$ and right extension $T[i\, ... j+1]$ are unique in $T$. Th e number of net occurrences of $S$ in $T$ is called its net frequency. Com pared with ordinary frequency\, net frequency highlights the more signific ant occurrences of $S$ in $T$. In this talk\, I will present several prope rties of net occurrences and describe techniques to identify all the net o ccurrences in Fibonacci and Thue-Morse words. In particular\, I will expla in the technique to characterize the occurrences of smaller-order Fibonacc i and Thue-Morse words. This is a joint work with Peaker Guo. URL:https://cow-seminar.github.io/archives/2025.html#20250916-kishi END:VEVENT BEGIN:VEVENT UID:20251014-julien@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20251014T130000Z DTEND:20251014T140000Z SUMMARY:Antoine Julien: On balance properties of hypercubic billiard words DESCRIPTION:This presentation is concerned with hypercubic billiards with i rrational trajectories. In this talk\, I will present the relationship bet ween balance properties in hypercubic billiards\, and subshift cohomology. \n\nMore precisely\, I will define cohomology for subshifts and (time perm itting) illustrate with examples of how cohomology has previously been use d in symbolic dynamics. Then\, I will present the link between cohomology and balance for billiard sequences. Finally\, I will explain how results o f Kellendonk and Sadun on the dimension of some cohomology spaces implies that billiard words in cubes of dimension at least 3 cannot be balanced on all factors.\n\nIn the case of billiards in the cube\, we also showed (us ing other methods) that these sequences are not balanced on factors of len gth 2.\n\nJoint work with Nicolas Bédaride and Valérie Berthé. URL:https://cow-seminar.github.io/archives/2025.html#20251014-julien END:VEVENT BEGIN:VEVENT UID:20251111-vanhatalo@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20251111T140000Z DTEND:20251111T150000Z SUMMARY:Aleksi Vanhatalo: Exponents of words under injective morphisms DESCRIPTION:A very common problem type in combinatorics on words is to cons truct words (under constraints) that avoid repetition. This is often done by constructing suitable morphisms.\nHere we flip the setup: we ask how go od morphisms are at introducing repetitions into words. Periodic morphisms are trivially very good at this\, but how about less trivial classes of m orphisms?\n\nWe consider a few variations of this question. We characteriz e finite words that do not have an upper bound on fractional or integer ex ponents when mapped via injective morphisms. Then we consider the asymptot ic critical exponent of infinite words. While we consider all finite alpha bet sizes\, these variations are better understood in the binary case.\nTh is talk is an extended version of the one presented at DLT 2025. It is bas ed on joint work with Eva Foster and Aleksi Saarela\, and on ongoing resea rch. URL:https://cow-seminar.github.io/archives/2025.html#20251111-vanhatalo END:VEVENT BEGIN:VEVENT UID:20251125-mollo@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20251125T140000Z DTEND:20251125T150000Z SUMMARY:Ignacio Mollo: Is fully shuffling a rational operation? DESCRIPTION:A shuffler is a 3-tape transducer specialized in the shuffling of words. These automata define rational sets in the so-called shuffling m onoid\, which map directly to regular shuffle languages. In this talk we l ook at rational relations of words and wonder whether their full shuffle i s rational: we conclude that it's very rare that the full shuffle of a rat ional relation remains rational but find very interesting examples where r ationality can be assured. URL:https://cow-seminar.github.io/archives/2025.html#20251125-mollo END:VEVENT BEGIN:VEVENT UID:20251209-manea@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20251209T140000Z DTEND:20251209T150000Z SUMMARY:Florin Manea: Linear Time Subsequence and Supersequence Regex Match ing DESCRIPTION:It is well-known that checking whether a given string $w$ match es a given regular expression $r$ can be done in quadratic time $O(|w|⋅ |r|)$ and that this cannot be improved to a truly subquadratic running tim e of $O((|w|⋅ |r|)^{1-\\varepsilon})$ assuming the strong exponential ti me hypothesis (SETH). We study a different matching paradigm where we ask instead whether $w$ has a subsequence that matches $r$\, and show that reg ex matching in this sense can be solved in linear time $O(|w| + |r|)$. Fur ther\, the same holds if we ask for a supersequence. We show that the quan titative variants where we want to compute a longest or shortest subsequen ce or supersequence of w that matches $r$ can be solved in $O(|w|⋅ |r|)$ \, i. e.\, asymptotically no worse than classical regex matching\; and we show that $O(|w| + |r|)$ is conditionally not possible for these problems. We also investigate these questions with respect to other natural string relations like the infix\, prefix\, left-extension or extension relation i nstead of the subsequence and supersequence relation. We further study the complexity of the universal problem where we ask if all subsequences (or supersequences\, infixes\, prefixes\, left-extensions or extensions) of an input string satisfy a given regular expression.\n\nThis is based on the paper: Antoine Amarilli\, Florin Manea\, Tina Ringleb\, Markus L. Schmid: Linear Time Subsequence and Supersequence Regex Matching. MFCS 2025: 9:1-9 :19 URL:https://cow-seminar.github.io/archives/2025.html#20251209-manea END:VEVENT BEGIN:VEVENT UID:20260106-marin@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260106T140000Z DTEND:20260106T150000Z SUMMARY:Louis Marin: Maximal 2-dimensional binary words of bounded degree DESCRIPTION:(Authors: Alexandre Blondin Massé\, Alain Goupil\, Raphael L'H eureux\, Louis Marin)\n\nLet $d$ be an integer between $0$ and $4$\, and $ W$ be a $2$-dimensional word of dimensions $h \\times w$ on the binary alp habet $\\{0\, 1\\}$\, where $h\, w \\in \\mathbb Z_{>0}$. Assume that each occurrence of the letter $1$ in $W$ is adjacent to at most $d$ letters $1 $. We provide an exact formula for the maximum number of letters $1$ that can occur in $W$ for fixed $(h\, w)$. As a byproduct\, we deduce an upper bound on the length of maximum snake polyominoes contained in a $h \\times w$ rectangle. URL:https://cow-seminar.github.io/#20260106-marin END:VEVENT BEGIN:VEVENT UID:20260120-kreczman@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260120T140000Z DTEND:20260120T150000Z SUMMARY:Savinien Kreczman: Factor complexity and critical exponent of words in a Thue-Morse family DESCRIPTION:The Thue-Morse\, Fibonacci-Thue-Morse and Allouche-Johnson word s are related to the binary\, Zeckendorf and Narayana numeration systems r espectively\, as they count the parity of the number of ones in representa tions of natural numbers in those systems. These three numeration systems can be seen as the special cases for $k=1\,2\,3$ of a positional numeratio n system based on the recurrence relation $U_n=U_{n-1}+U_{n-k}$. As such\, the three words above can be seen as the first elements in a family of bi nary words related to those numeration systems.\n\nIn a recent preprint\, J. Shallit put forth two conjectures on words of this family\, the first c oncerning the first difference of their factor complexity and the second c oncerning their asymptotic critical exponent. In this talk\, we will prove both conjectures by studying bispecial factors within those words. We wil l highlight a method by K. Klouda allowing us to fully list those bispecia l factors and show how this list allows us to attack the conjectures in qu estion. Joint work with Ľubomíra Dvořáková and Edita Pelantová. URL:https://cow-seminar.github.io/#20260120-kreczman END:VEVENT BEGIN:VEVENT UID:20260203-huch@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260203T140000Z DTEND:20260203T150000Z SUMMARY:Annika Huch: A Word Reconstruction Problem for Polynomial Regular L anguages DESCRIPTION:The reconstruction problem concerns the ability to uniquely det ermine an unknown word from querying information on the number of occurren ces of chosen subwords. In the joined work with M. Golafshan and M. Rigo w e focused on the reconstruction problem when the unknown word belongs to a known polynomial regular language\, i.e.\, its growth function is bounded by a polynomial. Exploiting the combinatorial and structural properties o f these languages\, we are able to translate queries into polynomial equat ions and transfer the problem of unique reconstruction to finding those se ts of queries such that their polynomial equations have a unique integer s olution. URL:https://cow-seminar.github.io/#20260203-huch END:VEVENT BEGIN:VEVENT UID:20260217-robertson@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260217T140000Z DTEND:20260217T150000Z SUMMARY:Steven Robertson: Number walls of automatic sequences DESCRIPTION:Given any one-dimensional sequence S\, one can generate a uniqu e two-dimensional sequence by considering the determinants of the Toeplitz matrices defined by S. This is known as the number wall of S. It is conje ctured that if S is automatic\, then the number wall of S is itself a two- dimensional automatic sequence. In this talk\, we will discuss evidence to wards this conjecture as well as some recent partial results. The talk aim s to be accessible for people with no experience of number walls. URL:https://cow-seminar.github.io/#20260217-robertson END:VEVENT BEGIN:VEVENT UID:20260303-vukusic@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260303T140000Z DTEND:20260303T150000Z SUMMARY:Ingrid Vukusic: Balanced rectangles over Sturmian words DESCRIPTION:One of the many properties of the famous infinite Fibonacci wor d $01001010\\cdots$ is that it is balanced. This means that any two blocks of the same length have either the same weight or their weights are off b y $1$. Results by Berthé and Tijdeman show that a 2-dimensional variant o f the Fibonacci word cannot be balanced. However\, for certain pairs $(m\, n)$\, the $m\\times n$ rectangles are balanced\, and recently all such $(m \,n)$ were fully characterised. We extend this characterisation to complet ely general Sturmian words. The proof is based on Diophantine approximatio n\, and I will explain why Ostrowski representations are “everything one could wish for”. URL:https://cow-seminar.github.io/#20260303-vukusic END:VEVENT BEGIN:VEVENT UID:20260317-richomme@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260317T140000Z DTEND:20260317T150000Z SUMMARY:Gwenaël Richomme: On some 2-binomial coefficients of binary words: geometrical interpretation\, partitions of integers\, and fair words DESCRIPTION:The binomial notation $\\binom{w}{u}$ represents the number of occurrences of the word $u$ as a (scattered) subword in $w$. We first intr oduce and study possible uses of a geometrical interpretation of $\\binom{ w}{ab}$ and $\\binom{w}{ba}$ when $a$ and $b$ are distinct letters. We the n study the structure of the $2$-binomial equivalence class of a binary wo rd $w$ (two words are $2$-binomially equivalent if they have the same bino mial coefficients\, that is\, the same numbers of occurrences\, for each w ord of length at most $2$). Especially we explain the existence of an isom orphism between the graph of the $2$-binomial equivalence class of $w$ wit h respect to a particular rewriting rule and the lattice of partitions of the integer $\\binom{w}{ab}$ with $\\binom{w}{a}$ parts and greatest part bounded by $\\binom{w}{b}$. Finally we study binary fair words\, the words over $\\{a\, b\\}$ having the same numbers of occurrences of $ab$ and $ba $ as subwords $\\left(\\binom{w}{ab} = \\binom{w}{ba}\\right)$. In particu lar\, we sketch a proof of a recent conjecture related to a special case o f the least square approximation. URL:https://cow-seminar.github.io/#20260317-richomme END:VEVENT BEGIN:VEVENT UID:20260331-bernales@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260331T130000Z DTEND:20260331T140000Z SUMMARY:Paulina Cecchi Bernales: Interplay between combinatorics and dynami cal properties in minimal symbolic systems DESCRIPTION:Symbolic systems\, also known as subshifts\, are topological dy namical systems whose phase space consists of infinite sequences of symbol s\, evolving under the action of the (left) shift transformation. As infin ite words\, the elements of a symbolic system possess combinatorial proper ties associated with their language\, and it is natural to ask how these c ombinatorial properties determine or interact with the properties of the s ystem as a dynamical system\, or vice versa. In this talk\, I will briefly review the basic notions of symbolic systems and some classical results w hich connect their combinatorial and dynamical properties\, particularly f or subshifts generated by substitutions. I will then present more recent r esults illustrating the impact of combinatorics on the spectral properties of minimal subshifts. In these results\, combinatorial objects such as ex tension graphs or coboundaries will play an important role. This is a part of a joint work with V. Berthé and B. Espinoza. URL:https://cow-seminar.github.io/#20260331-bernales END:VEVENT BEGIN:VEVENT UID:20260414-kabore@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260414T130000Z DTEND:20260414T140000Z SUMMARY:Idrissa Kaboré: On modulo-recurrence and window complexity in infi nite words DESCRIPTION:In this talk\, first\, I will recall the notions of modulo-recu rrent words and of window complexity. These notions are introduced in 2007 . Then\, I present some properties of these notions. After that\, I will p resent the notions of uniform modulo-recurrence and of strong modulo-recur rence. These notions are defined recently in a joint work with Julien Cass aigne. Sturmian words are uniformly (resp. strongly) modulo-recurrent word s. Then\, I will address the window complexity of the Thue-Morse. To finis h\, I will present a recurrent aperiodic word with bounded window complexi ty. URL:https://cow-seminar.github.io/#20260414-kabore END:VEVENT BEGIN:VEVENT UID:20260428-espinoza@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260428T130000Z DTEND:20260428T140000Z SUMMARY:Bastiàn Espinoza: The Thue-Morse word in base 3/2 DESCRIPTION:A rich family of symbolic dynamical systems of low complexity i s given by automatic sequences. These sequences are obtained by feeding th e base-$k$ expansions of integers\, for a fixed integer base $k$\, into a finite automaton. In this talk\, we turn to automatic sequences in rationa l bases\, using as a guiding example a rational-base analogue of one of th e most classical integer-base automatic words. Namely\, we consider the Th ue–Morse word in base $3/2$\, whose $n$-th term is given by the sum modu lo 2 of the digits in the base-$3/2$ representation of $n$. Our results sh ow that\, although this base-$3/2$ variant is substantially more complex t han classical automatic words (for instance\, it is not generated by itera ting a single substitution\, and its factor complexity grows superlinearly ) it nevertheless retains several characteristic properties of the integer -automatic world. More precisely\, we prove uniform recurrence\, establish the existence of letter frequencies\, and show several combinatorial symm etries of its language analogous to those of the classical base-2 word. Ou r approach relies on describing the word via the periodic iteration of two substitutions\, studying the induced action of these substitutions on the $2$-adic integers\, and applying Pontryagin duality on this group.\n\nThi s is joint work with Julien Cassaigne\, Michel Rigo\, and Manon Stipulanti . URL:https://cow-seminar.github.io/#20260428-espinoza END:VEVENT BEGIN:VEVENT UID:20260512-vivion@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260512T130000Z DTEND:20260512T140000Z SUMMARY:Léo Vivion: New examples of words for which binomial complexities and subword complexity coincide DESCRIPTION:In 2015\, Rigo and Salimov introduced a family of complexities that forms a scale between abelian complexity and factor complexity: the $ k$-binomial complexities. In particular\, they showed that Sturmian words satisfy the following remarkable combinatorial property: their $2$-binomia l complexity is equal to their factor complexity. Since then\, the only ot her known example satisfying this property is the Tribonacci word.\n\nIn t his talk\, I will present some stability results for words whose $k$-binom ial complexities coincide with their factor complexity\, notably under let ter deletion and a coloring operation. These stability properties allow to show that several well-known families of words also have their $2$-binomi al complexity equal to their factor complexity. URL:https://cow-seminar.github.io/#20260512-vivion END:VEVENT BEGIN:VEVENT UID:20260609-dvorakova@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260609T130000Z DTEND:20260609T140000Z SUMMARY:Ľubomíra Dvořáková: Attractors of sequences coding beta-intege rs DESCRIPTION:String attractor is an intensively studied object in Combinator ics on Words. In our talk\, we will recall known results and also some pre viously used techniques. We will then describe minimal string attractors o f prefixes of simple Parry sequences. These sequences form a coding of dis tances between consecutive beta-integers in numeration systems with a real base beta. Simple Parry sequences have been recently studied from this po int of view and (not necessarily minimal) attractors of their prefixes hav e been described and a conjecture that attractors of alphabet size should be sufficient was stated. We prove this conjecture. Moreover\, we provide attractors of prefixes of some particular form of binary non-simple Parry sequences. URL:https://cow-seminar.github.io/#20260609-dvorakova END:VEVENT BEGIN:VEVENT UID:20260623-cloitre@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260623T130000Z DTEND:20260623T140000Z SUMMARY:Benoit Cloitre: The Thue-Morse Transform DESCRIPTION:We define a transform $T$ on binary words. Given a binary word\ , we use the positions of its zeros and ones to build a new binary word. A pplied to the alternating word $a_0 = 0101\\ldots$\, the transform gives t he Thue-Morse word. We then study the orbit $a_m = T^m(a_0)$\, together wi th the sequences $u_m$ and $v_m$ giving the positions of the ones and the zeros in $a_m$. We obtain an explicit formula for $a_m(n)$ in terms of the binary digits of $n$ and $m-1$. From this formula we derive Prouhet-Tarry -Escott identities\, composition formulas that generalize the identities f or evil and odious numbers\, and a recurrence formula for the factor compl exity of $a_m$. We end with a few directions\, such as applying the transf orm to the Fibonacci word\, which yields the Fibonacci-Thue-Morse word. URL:https://cow-seminar.github.io/#20260623-cloitre END:VEVENT BEGIN:VEVENT UID:20260915-yassawi@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260915T130000Z DTEND:20260915T140000Z SUMMARY:Reem Yassawi: Cobham’s theorem for Gaussian numerations DESCRIPTION:Possibly the most important theorem concerning automatic sequen ces is Cobham’s theorem\, first proved in 1969. Very roughly speaking\, it says that the base-$k$ and base-$l$ expansions of natural numbers canno t be correlated if $k$ and $l$ are multiplicately independent\, i.e.\, if there do not exist $m$ and $n$ such that $k^m = l^n$. Precisely\, a sequen ce $a = (a_n)_{n\\ge 0}$ is $k$-automatic if $a_n$ is a finite-state funct ion of the base-$k$ expansion of $n$. Cobham’s theorem states that if $k $ and $l$ are multiplicatively independent\, then a sequence is both $k$- and $l$-automatic if and only if it is eventually periodic.\n\nOne can als o consider Cobham’s theorem for Euclidean domains\, such as the Gaussian integers $\\mathbb Z[i]$. In 2003\, Hansel and Safer considered $\\alpha = -m+i$ as a base for Gaussian numeration systems $(m \\ge 1)$\, with digi ts from the set $\\{0\, 1\, \\dots\, m^2\\}$. Any two Gaussian integers of this form must be multiplicatively independent. Assuming the four exponen tials conjecture\, Hansel and Safer showed that for such Gaussian integers $\\alpha$ and $\\beta$\, if the characteristic function of an infinite $S \\subset \\mathbb Z[i]$ is both $\\alpha$- and $\\beta$-recognizable\, th en it must be syndetic. They conjectured that this set must be eventually periodic.\n\nIn this talk I will describe how we can prove the following v ersion of Cobham’s theorem\, for the largest possible family of Gaussian numerations\, with any generating finite digit set and without using the four exponentials conjecture. We show that if $|\\alpha| > 1$ and $|\\beta | > 1$ are multiplicatively independent\, and if one of the Gaussian integ ers $\\alpha\, \\beta$ is not the root of an integer\, then any sequence $ (a_z)_{z\\in\\mathbb Z[i]}$ that is both $\\alpha$- and $\\beta$-automatic must be eventually periodic. In particular\, Hansel and Safer’s conject ure is proved true. The requirement that one of $\\alpha$ and $\\beta$ mus t be a root of an integer cannot be relaxed. This is joint work with Álva ro Bustos-Gajardo and Robbert Fokkink. URL:https://cow-seminar.github.io/#20260915-yassawi END:VEVENT BEGIN:VEVENT UID:20260929-frid@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20260929T130000Z DTEND:20260929T140000Z SUMMARY:Anna Frid: Palindromic length in free groups\, Catalan expressions\ , and new risks for mathematicians DESCRIPTION:We characterize words of a given palindromic length in a free g roup in terms of Catalan expressions. Also\, we discuss why publishing tit les of future talks before the preprint is online can be risky nowadays.\n \nThis is a joint work with Volker Diekert\, Silas Natterer and Alexander Thumm. URL:https://cow-seminar.github.io/#20260929-frid END:VEVENT BEGIN:VEVENT UID:20261013-kosoy@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20261013T130000Z DTEND:20261013T140000Z SUMMARY:Vanessa Kosoy: Stringological sequence prediction DESCRIPTION:This talk is about a newly discovered connection between combin atorics on words and the sequence prediction problem in machine learning. The sequence prediction problem asks to provide an algorithm which\, given the prefix of a word\, guesses the next symbol in some “intelligent” way. The natural interpretation of “intelligent” is to require that on “simple” words – i.e. words that have simple patterns – the algor ithm makes few mistakes. Formally\, it means that we specify a “complexi ty measure” which is a function from words to numbers\, and require a bo und on the number of mistakes in terms of the complexity. We also want the algorithm to be fast and use little space on words of low complexity (bec ause such words should be compressible). In this talk\, I will formalize t hese requirements and show that it is possible to meet them for several na tural complexity measures coming from combinatorics on words\, for which n atural classes of sequences have slowly growing complexity. Two examples o f such measures are left-to-right and right-to-left k-automaticity\, so th e corresponding prediction algorithms work well on k-automatic sequences. Another example is the size of the smallest straight-line program for a wo rd\, leading to an algorithm that works well for morphic and Sturmian sequ ences. Additional examples are complexity measures that were invented for this line of research\, related to the “mix-automatic” sequences of En drullis et al. Many open problems remain\, both on the algorithms side and the combinatorics side. URL:https://cow-seminar.github.io/#20261013-kosoy END:VEVENT BEGIN:VEVENT UID:20261027-coons@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20261027T140000Z DTEND:20261027T150000Z SUMMARY:Michael Coons: Correlations of the Thue-Morse Sequence DESCRIPTION:We revisit the pair correlations of the Thue–Morse sequence w ith focus on asymptotic results on various means. In the first part of the talk\, we will show that all higher-order correlations of the Thue–Mors e sequence with general real weights are effectively determined by a singl e value of the balanced $2$-point correlation. As a consequence\, we get t hat all odd-order correlations of the balanced Thue–Morse sequence vanis h\, and that\, for any even $n$\, the $n$-point correlations of the balanc ed Thue–Morse sequence have mean value zero\, as do their absolute value s\, raised to an arbitrary positive power. We will then show how the corre lations of the Thue–Morse sequence with general real weights can be deri ved from the balanced $2$-point correlations. In the second/last part of t he talk\, we will focus on understanding the growth of the sum of the abso lute values of the autocorrelations. This is joint work with Michael Baake \, Jan Mazac\, Ari Pincus-Kazmar and Adam Stout. URL:https://cow-seminar.github.io/#20261027-coons END:VEVENT BEGIN:VEVENT UID:20261110-bell@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20261110T140000Z DTEND:20261110T150000Z SUMMARY:Jason Bell DESCRIPTION: URL:https://cow-seminar.github.io/#20261110-bell END:VEVENT BEGIN:VEVENT UID:20261124-rue@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20261124T140000Z DTEND:20261124T150000Z SUMMARY:Thierry de la Rue: Frequency of patterns in smooth sequences over t he alphabet $\\{1\,3\\}$ DESCRIPTION:The famous Oldenburger-Kolakoski sequence is an example of a sm ooth sequence over $\\{1\,2\\}$\, that is a sequence on which we can itera te the run-length encoding operation while sticking to the same alphabet. The very existence of the frequency of “$1$”s in this sequence has bee n the subject of an open question for decades.\n\nIn this talk\, based on a joint work with Damien Jamet\, Irène Marcovici and Léo Poirier\, I wil l show that smooth sequences over the alphabet $\\{1\,3\\}$ are much easie r to analyze. Indeed these sequences hide a substitutive structure that we use to demonstrate the following result: The subshift of smooth sequences over $\\{1\,3\\}$ is partitioned into continuously many uniquely ergodic subshifts. As a consequence\, the asymptotic frequency of any finite patte rn in a given smooth sequence over $\\{1\,3\\}$ is always well-defined and depends only on its so-called “type sequence“. I will also discuss th e minimality of these subshifts. URL:https://cow-seminar.github.io/#20261124-rue END:VEVENT BEGIN:VEVENT UID:20261208-hughes@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20261208T140000Z DTEND:20261208T150000Z SUMMARY:Christian B. Hughes: Clustering of Return Words in the Languages of Arbitrary Standard IETs DESCRIPTION:Interval exchange transformations (IETs) are dynamical systems that rearrange finitely many sub-intervals of an interval\; their symbolic codings admit languages with rich combinatorial properties. We study retu rn words in IET languages and their connection to the Burrows-Wheeler tran sform\, a word transform often employed in text pre-compression\, and show \, via stepwise morphisms attached to an extended induction on IETs\, that every return word in the language of an arbitrary standard IET is cluster ing with respect to the IET's defining permutation\, in turn answering a q uestion of Mélodie Lapointe. URL:https://cow-seminar.github.io/#20261208-hughes END:VEVENT BEGIN:VEVENT UID:20261222-shallit@cow-seminar.github.io DTSTAMP:20261014T193305Z DTSTART:20261222T140000Z DTEND:20261222T150000Z SUMMARY:Jeffrey O. Shallit: LLM's and Combinatorics on Words DESCRIPTION:This talk will consist of three parts. In the first part\, I'll briefly survey some new results that I and my co-authors have obtained th is year by using various LLM's. You can see some of them on my page https: //cs.uwaterloo.ca/~shallit/papers.html where an asterisk at the start of a n entry means we used an LLM to obtain some or all of the results.\n\nIn t he second part\, I'll mention a list of issues that this new\, powerful te chnology raises for mathematics in general\, and combinatorics on words in particular.\n\nIn the third part\, I'll throw it open to an open-ended au dience discussion of the issues\, so if you have been following what's goi ng on\, please think in advance about questions and issues you might want to discuss. URL:https://cow-seminar.github.io/#20261222-shallit END:VEVENT END:VCALENDAR