BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Lucas Mol (University of Winnipeg)
DTSTART:20200629T130000Z
DTEND:20200629T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/1
DESCRIPTION:Title: Extremal Square-Free Words and Variations\nby Lucas Mol (
University of Winnipeg) as part of One World Combinatorics on Words Semina
r\n\n\nAbstract\nA square-free word $w$ over a fixed alphabet $\\Sigma$ is
extremal if every word obtained from $w$ by inserting a single letter fro
m $\\Sigma$ (at any position) contains a square. Grytczuk et al. recently
introduced the concept of extremal square-free word\, and demonstrated tha
t there are arbitrarily long extremal square-free words over a ternary alp
habet. One can define extremal overlap-free words\, and more generally\, e
xtremal $\\beta$-free words\, analogously. We characterize the lengths of
extremal square-free ternary words\, and the lengths of extremal overlap-f
ree binary words. We also establish that there are arbitrarily long extrem
al $\\beta$-free binary words for every $2 < \\beta \\leq 8/3$. We include
a variety of interesting conjectures and open questions.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Rigo (University of Liège)
DTSTART:20200713T130000Z
DTEND:20200713T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/2
DESCRIPTION:Title: Binomial^3 : coefficients\, equivalence\, complexity…\
nby Michel Rigo (University of Liège) as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nThe 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.\, Sim
on's congruence\, Parikh matrices\, reconstruction problem\, ... A few yea
rs ago\, we introduced the $k$-binomial equivalence: Two words $u$ and $v$
are $k$-binomially equivalent if the binomial coefficients $u \\choose x$
and $v \\choose x$ agree for all words $x$ of length up to $k$. This is a
refinement of the usual abelian equivalence.\n\nFirst\, I will review sev
eral results (joint work with P. Salimov\, M. Lejeune\, J. Leroy\, M. Rose
nfeld) related to $k$-binomial complexity (where factors of length $n$ are
counted up to $k$-binomial equivalence) for Sturmian words\, Thue-Morse w
ord and Tribonacci word. Then I will concentrate on $k$-binomial equivalen
ce classes for finite words. In particular\, I will discuss the fact that
the submonoid generated by the generators of the free nil-$2$ group on $m$
generators is isomorphic to the quotient of the free monoid $\\{1\,...\,m
\\}^∗$ by the $2$-binomial equivalence (joint work with M. Lejeune\, M.
Rosenfeld).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laurent Vuillon (University of Savoie)
DTSTART:20200720T130000Z
DTEND:20200720T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/3
DESCRIPTION:Title: Combinatorics on words for Markoff numbers\nby Laurent Vu
illon (University of Savoie) as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nMarkoff numbers are fascinating integers related to
number\ntheory\, Diophantine equation\, hyperbolic geometry\, continued fr
actions\nand Christoffel words. Many great mathematicians have worked on t
hese\nnumbers and the $100$ years famous uniqueness conjecture by Frobeniu
s is\nstill unsolved. In this talk\, we state a new formula to compute the
\nMarkoff numbers using iterated palindromic closure and the Thue-Morse\ns
ubstitution. The main theorem shows that for each Markoff number $m$\,\nth
ere exists a word $v\\in \\{a\,b\\}^*$ such that $m−2$ is equal to the l
ength of the iterated palindromic\nclosure of the iterated antipalindromic
closure of the word $av$. This\nconstruction gives a new recursive constr
uction of the Markoff numbers\nby the lengths of the words involved in the
palindromic closure.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:James Currie (University of Winnipeg)
DTSTART:20200727T130000Z
DTEND:20200727T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/4
DESCRIPTION:Title: Remarks on Pansiot encodings\nby James Currie (University
of Winnipeg) as part of One World Combinatorics on Words Seminar\n\n\nAbs
tract\nPansiot encodings were an essential ingredient in the solution of D
ejean's conjecture. We discuss these encodings\, and the related group the
oretic notions\, in a way perhaps more natural to combinatorics on words\,
namely\, in terms of De Bruijn graphs. We discuss variations on Pansiot e
ncodings\, with applications to circular words\, and to the undirected thr
eshold problem.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Reem Yassawi (The Open University)
DTSTART:20200914T130000Z
DTEND:20200914T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/5
DESCRIPTION:Title: The Ellis semigroup of bijective substitution shifts\nby
Reem Yassawi (The Open University) as part of One World Combinatorics on W
ords Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jarkko Peltomäki (University of Turku)
DTSTART:20200928T130000Z
DTEND:20200928T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/6
DESCRIPTION:Title: Avoiding abelian powers cyclically\nby Jarkko Peltomäki
(University of Turku) as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nA finite word $w$ avoids abelian $N$-powers cyclically if f
or each\nabelian $N$-power of period $m$\, we have $m \\geq |w|$. This not
ion\ngeneralizes circular avoidance of $N$-powers in two ways. Firstly\n"p
ower" is replaced by "abelian power" and secondly circular avoidance\nconc
erns 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$ ther
e exists a word of length $n$ over a $k$-letter alphabet that\navoids abel
ian $N$-powers cyclically. Let $\\mathcal{A}_\\infty(k)$ be the\nleast int
eger $N$ such that there exist arbitrarily long words over a\n$k$-letter a
lphabet that avoid abelian $N$-powers cyclically.\n\nI will sketch the pro
ofs 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$\, $\\ma
thcal{A}(k) = 2$ for $k \\geq 5$\; 2)\n$\\mathcal{A}_\\infty(2) = 4$\, $\\
mathcal{A}_\\infty(3) = 3$\, and\n$\\mathcal{A}_\\infty(4) = 2$. If time p
ermits\, I will discuss an\napplication to the growth rates of exponents o
f abelian powers occurring\nin infinite binary words.\n\nSorry\, no video
available\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jarosław Grytczuk (The Jagiellonian University)
DTSTART:20201005T130000Z
DTEND:20201005T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/7
DESCRIPTION:Title: Graph Coloring and Combinatorics on Words\nby Jarosław G
rytczuk (The Jagiellonian University) as part of One World Combinatorics o
n Words Seminar\n\n\nAbstract\nI will present a few problems inspired mutu
ally by various issues studied in the two disciplines of the title. For in
stance\, given any sequence of 3-letter alphabets\, is it possible to pick
a letter from each alphabet so that the resulting word is {\\it square-fr
ee}? The case of equal alphabets is covered by the famous result of Thue\,
but intuition tells us that this should be the hardest case (the more dif
ferent letters in the play\, the easier to avoid repeated factors). While
more than one has attacked the problem\, the question remains unanswered\,
which is especially frustrating as it has a positive answer with 4-letter
alphabets.\n\nThe above question was originally motivated by the {\\it li
st coloring} problem\, a very popular topic in graph coloring. However\, t
he opposite direction of inspiration also leads to intriguing matters. For
example\, how many letters are needed to label the vertices of a {\\it pl
anar graph} so that any word occurring along a simple path is square-free?
It has been recently proved that 768 letters suffice\, but for a long tim
e it was not known if any finite alphabet will do. Perhaps results of that
type could be applied back to some pattern avoidability issues...?\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Dekking (Technische Universiteit Delft)
DTSTART:20201019T130000Z
DTEND:20201019T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/8
DESCRIPTION:Title: The structure of Zeckendorf representations and base $\\varph
i$ expansions\nby Michel Dekking (Technische Universiteit Delft) as pa
rt of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn the Zecke
ndorf numeration system natural numbers are represented as sums of Fibonac
ci numbers. In base $\\varphi$ natural numbers are represented as sums of
powers of the golden mean $\\varphi$. Both representations have digits 0 a
nd 1\, where the word 11 is not allowed. We know that the Fibonacci number
s\, and the powers of $\\varphi$ are closely related\, as\, for example\,
in the relation $\\varphi^n=F_{n-1}+F_n\\varphi$. In fact\, Frougny and Sa
karovitch have shown that Zeckendorf representations can be transformed to
base $\\varphi$ expansions by a 2-tape automaton. I will take a direct ap
proach: what are the words that can occur in the Zeckendorf representation
s\, and what are those that occur in base $\\varphi$ expansions? In which
representations/expansions\, of which natural numbers do they occur?\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthieu Rosenfeld (LIS\, Marseille\, France)
DTSTART:20201026T140000Z
DTEND:20201026T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/9
DESCRIPTION:Title: A simple proof technique to study avoidability of repetitions
\nby Matthieu Rosenfeld (LIS\, Marseille\, France) as part of One Worl
d Combinatorics on Words Seminar\n\n\nAbstract\nI recently described a new
proof technique that I used to study nonrepetitive colorings of graphs. T
his technique is in fact more general and seems to be as powerful as the L
ovász local lemma or the entropy compression method. For instance\, it h
as since been used by D.R. Wood and I.M. Wanless in the context of boolea
n satisfiability problem and of hypergraph colorings. In the particular co
ntext of combinatorics on words similar approaches had already been used b
y different authors\, but were never extended to graphs or other structure
s.\n\nIn this talk\, I will first present some simple applications of the
method to combinatorics on words and I will then explain how to extend thi
s approach to nonrepetitive colorings of graphs of bounded degree.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Eric Rowland (Hofstra University)
DTSTART:20201109T140000Z
DTEND:20201109T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/10
DESCRIPTION:Title: Avoiding fractional powers on an infinite alphabet\nby E
ric Rowland (Hofstra University) as part of One World Combinatorics on Wor
ds Seminar\n\n\nAbstract\nQuestions concerning avoidability of patterns ha
ve been central to combinatorics on words since the work of Thue. In 2009\
, Guay-Paquet and Shallit gave several results about pattern avoidance of
words on the alphabet of natural numbers. Most patterns are avoidable on t
his alphabet\, but it is interesting to ask about the lexicographically le
ast word that avoids a pattern. For fractional powers\, often this word is
generated by a relatively simple morphism. In recent work with Manon Stip
ulanti\, we discovered the structure of the lexicographically least 5/4-po
wer-free word on the natural numbers. In a surprising departure from previ
ously studied words\, the morphism generating this word does not preserve
5/4-power-freeness.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Émilie Charlier (University of Liège)
DTSTART:20201123T140000Z
DTEND:20201123T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/11
DESCRIPTION:Title: Regular sequences in abstract numeration systems\nby Ém
ilie Charlier (University of Liège) as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nAn abstract numeration system $S$ is given b
y a regular language $L$ over a totally ordered alphabet $(A\,<)$. The num
eration language $L$ is ordered thanks to the radix (or genealogical) orde
r induced by $<$. A natural number $n$ is then represented by the $n$-th w
ord of the language (where we start counting from $n=0$). Integer bases $b
$ and numeration systems based on a linear base sequence $U$ with a regula
r numeration language are examples of abstract numeration systems. The not
ion of $b$-regular sequences was extended to abstract numeration systems b
y Maes and Rigo. Their 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 alternative definition of $S$-regular sequences\, that permits us
to use recognizable formal series in order to generalize most (if not all
) known characterizations of $b$-regular sequences. I will also show that
an extra characterization can be obtained in the case of Pisot numeration
systems. Finally\, I will consider the special cases of $S$-automatic and
$S$-synchronized sequences. In particular\, we will see that the factor co
mplexity of an $S$-automatic sequence defines an $S$-regular sequence. Thi
s is a joint work with Célia Cisternino and Manon Stipulanti.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marie Lejeune (University of Liège)
DTSTART:20201207T140000Z
DTEND:20201207T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/12
DESCRIPTION:Title: Reconstructing words from right-bounded-block words\nby
Marie Lejeune (University of Liège) as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nIn this joint work with P. Fleischmann\, F.
Manea\, D. Nowotka\, and M. Rigo\, we study a variation of the famous reco
nstruction problem over words. It has been studied since $1973$. A survey
of the different results will be held in the talk.\n\nWe study a variation
of this problem.\nLet $\\mathcal{A}$ be a given alphabet and $n$ a natura
l number. We want to 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 t
ype "What is the multiplicity of $u_i$ as subword of $w$?". Based on the a
nswers 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 upp
er known bound for $k$-reconstructibility.\n\nWe will show how to reconstr
uct a binary word $w$ from $m+1$ questions\, where $m$ is the minimum numb
er of occurrences of {\\tt a} and {\\tt b} in the word. We then reduce the
problem for arbitrary finite alphabets to the binary case. We compare our
bounds to the best known one for the classical reconstruction problem.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sébastien Labbé (LaBRI\, Bordeaux\, France)
DTSTART:20201214T140000Z
DTEND:20201214T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/13
DESCRIPTION:Title: A characterization of Sturmian sequences by indistinguishabl
e asymptotic pairs\nby Sébastien Labbé (LaBRI\, Bordeaux\, France) a
s part of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe give
a new characterization of Sturmian configurations in terms of indistinguis
hable asymptotic pairs. Two asymptotic configurations on a full $\\mathbb{
Z}$-shift are indistinguishable if the sets of occurrences of every patter
n in each configuration coincide up to a finitely supported permutation. T
his characterization can be seen as an extension to biinfinite sequences o
f Pirillo's theorem which characterizes Christoffel words. Furthermore\, w
e provide a full characterization of indistinguishable asymptotic pairs on
arbitrary alphabets using substitutions and characteristic Sturmian seque
nces. The proof is based on the well-known notion of derived sequences.\n\
nThis is joint work with Sebastián Barbieri and Štěpán Starosta. Prepr
int is available at https://arxiv.org/abs/2011.08112\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anna Frid (Aix-Marseille Université)
DTSTART:20210104T140000Z
DTEND:20210104T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/14
DESCRIPTION:Title: Is not prefix palindromic length of a k -automatic word k
-regular?\nby Anna Frid (Aix-Marseille Université) as part of One Wor
ld Combinatorics on Words Seminar\n\n\nAbstract\nWe consider the function
of the prefix palindromic length for $k$-automatic words and prove that it
is $k$-regular for such words containing a finite number of distinct pali
ndromes\, like for example the paperfolding word. We also observe that in
the opposite case\, if the number of distinct palindromes is infinite\, th
is function can be $k$-regular\, as for the Thue-Morse word\, or seemingly
not\, as for the period-doubling word. The fact of non-regularity\, howev
er\, stays unproven.\n\nThis is a joint work with Enzo Laborde and Jarkko
Peltomäki.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean-Paul Allouche (CNRS\, IMJ-PRG\, Sorbonne Université\, Paris)
DTSTART:20210201T140000Z
DTEND:20210201T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/16
DESCRIPTION:Title: Hidden automatic sequences\nby Jean-Paul Allouche (CNRS\
, IMJ-PRG\, Sorbonne Université\, Paris) as part of One World Combinatori
cs on Words Seminar\n\n\nAbstract\nWe discuss a joint work with Michel Dek
king and Martine Queffélec (https://arxiv.org/abs/2010.00920) about seque
nces given as fixed points of non-uniform morphisms that happen to be actu
ally automatic.\n\nOne of the most ancien example is probably the one due
to Berstel\, who proved that the Istrail squarefree sequence defined as th
e fixed point of the morphism $f$ with $f(0) = 12$\, $f(1) = 102$\, $f(2)
= 0$ is also\n$2$-automatic.\n\nAfter revisiting an old criterion due to M
. Dekking at the end of the 70's\, we give several examples (in particular
of sequences in the OEIS). Finally we focus on morphisms associated with
Grigorchuk(-like) groups.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Petr Ambrož
DTSTART:20210215T140000Z
DTEND:20210215T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/17
DESCRIPTION:Title: Morphisms generating antipalindromic words\nby Petr Ambr
ož as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe
introduce two classes of morphisms over the alphabet\n$A=\\{0\,1\\}$ whose
fixed\npoints contain infinitely many antipalindromic factors. An\nantipa
lindrome 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 contain all morphism
s (up to\nconjugation) which generate infinite words with\ninfinitely many
antipalindromes. This is an analogue to the famous HKS\nconjecture concer
ning infinite words\ncontaining infinitely many palindromes. We prove our
conjecture for two\nspecial classes of morphisms\,\nnamely (i) uniform mor
phisms and (ii) morphisms with fixed points\ncontaining also infinitely ma
ny palindromes.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mickaël Postic
DTSTART:20210301T140000Z
DTEND:20210301T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/18
DESCRIPTION:Title: Open and closed complexity functions of infinite words\n
by Mickaël Postic as part of One World Combinatorics on Words Seminar\n\n
\nAbstract\nClosed words\, also known as complete first returns\, have bee
n studied for a long time\, and play an important role in symbolic dynamic
s. A word which is not closed is said to be open. In this talk based on a
joint work with Olga Parshina\, I will present a characterization of aperi
odic words in terms of their open complexity function and closed complexit
y function\, in the spirit of Morse and Hedlund's theorem. The preprint is
available at https://arxiv.org/pdf/2005.06254.pdf\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Szymon Stankiewicz
DTSTART:20210315T140000Z
DTEND:20210315T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/19
DESCRIPTION:Title: Square-free reducts of words\nby Szymon Stankiewicz as p
art of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe discuss
a joint work with Jarosław Grytczuk (https://arxiv.org/abs/2011.12822) ab
out square-free reducts of words.\n\nIn any finite word one may delete the
repeated block of a square\, obtaining thereby a shorter word. By repeati
ng this process\, a square-free word is eventually reached\, which we call
a reduct of the original word.\n\nWe will show that for each positive int
eger $n$ there is a word over ternary alphabet which can be reduced to at
least $n$ different words and also that there is a word over alphabet of s
ize four which has exactly $n$ reducts. We will also show that there exist
s infinitely many ternary words having exponential many reducts in the len
gth of these words.\n\nFor a fixed alphabet one can create a poset with no
des being words and $u > v$ iff word $u$ can be reduced to word $v$. We wi
ll describe some properties of those posets.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jacques Sakarovitch (RIF\, CNRS / Univ. de Paris and Télécom Par
is\, IPP)
DTSTART:20210329T130000Z
DTEND:20210329T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/20
DESCRIPTION:Title: From Fibonacci to golden mean representations\nby Jacque
s Sakarovitch (RIF\, CNRS / Univ. de Paris and Télécom Paris\, IPP) as p
art of One World Combinatorics on Words Seminar\n\n\nAbstract\nEvery posit
ive integer can be written as a sum of Fibonacci numbers\; this yields a F
ibonacci representation of the integer. A positive integer can also be wri
tten as a (finite) sum of (positive and negative) powers of the golden mea
n\; this yields a golden mean representation of the integer\, with the rad
ix point roughly in the middle of the writing. It is the golden mean expan
sion when it contains no consecutive digits equal to 1.\n\nWe show that th
ere exists a letter-to-letter finite two-tape automaton that maps the Fibo
nacci representation of any positive integer onto its golden mean expansio
n\, provided the latter is folded around the radix point. As a corollary\,
the set of golden mean expansions of the positive integers is a linear co
ntext-free language.\n\nThese results are generalised to the more general
case of integer representations in numeration systems built upon quadratic
Pisot units.\n\nJoint work with Christiane Frougny\, published in 1999 in
the Journal of Algebra and Computation. This talk is a follow-up to the o
ne of October 15 by Michel Dekking\, who kindly quoted this paper but deem
ed it hard to understand.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Valérie Goyheneche
DTSTART:20210412T130000Z
DTEND:20210412T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/21
DESCRIPTION:Title: Eigenvalues and constant arithmetical progressions for subst
itutive sequences\nby Valérie Goyheneche as part of One World Combina
torics on Words Seminar\n\n\nAbstract\nThe main subject of this talk is to
answer the following decidability question : does a substitutive sequence
$x$ admit a constant arithmetical progression $(x_{k+np})_n$?\n\nOur meth
od mainly relies on the link between constant arithmetical subsequences an
d (dynamical) eigenvalues of the underlying dynamical system.\nWe will exp
lain a method to compute the set of (additive) eigenvalues associated to s
uch systems.\nWe can then deduce\, given an integer $p$\, if the sequence
$x$ contains a constant arithmetical progression with period $p$.\nAt the
end of the talk\, we will focus on the case of primitive constant-length s
ubstitutions\, for which the set of such periods can be described by an au
tomaton.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luca Zamboni
DTSTART:20210426T130000Z
DTEND:20210426T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/22
DESCRIPTION:Title: Singular words\nby Luca Zamboni as part of One World Com
binatorics on Words Seminar\n\n\nAbstract\nThe extremal solutions to certa
in problems in the theory of finite continued fractions are characterised
by a special combinatorial property which we call the _singular_ property.
This property may be interpreted in the framework of finite words\, cycli
c words\, and one and two-sided infinite words over arbitrary ordered alph
abets. Each linear (resp. cyclic) word w is Abelian equivalent to a singul
ar linear (resp. cyclic) word w’ which is in general unique up to revers
al. We develop an algorithm for generating all singular words having a pr
escribed Parikh vector which is based in part on a non-commutative variant
of the usual Euclidean algorithm. This allows us to answer a question of
G. Ramharter from 1983 on the extremal values of the regular and semi-regu
lar cyclic continuants introduced by Motzkin and Straus in the 1950’s. W
e also confirm a conjecture of Ramharter in certain instances and exhibit
counter examples in other cases. As for infinite words\, the singular pro
perty in the context of bi-infinite binary words coincides with the Markof
f property which was shown by C. Reutenauer to be equivalent to the balanc
e property. We generalise this to higher alphabets by showing that the si
ngular property is the fundamental property which characterises the langu
age structure of codings of symmetric k-interval exchange transformations.
This is based on a collaboration with Alessandro De Luca and Marcia Edso
n initiated during the first Covid lockdown of 2020.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robert Mercas (Loughborough University)
DTSTART:20210208T140000Z
DTEND:20210208T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/23
DESCRIPTION:Title: (Trying to do a) Counting of distinct repetitions in words\nby Robert Mercas (Loughborough University) as part of One World Combin
atorics on Words Seminar\n\n\nAbstract\nThe topic of counting the distinct
repetitions that a word contains has been around for at least two decades
. The problem of counting distinct squares in a word was introduced by Fra
enkel and Simpson in ’98\, who also showed that their number is upper bo
unded 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 exist several improvements of their original resu
lt). Moreover\, recently Manea and Seki showed that proving the bound for
binary words is enough. Moreover\, further work was done on counting disti
nct repetitions of higher exponent with quite sharp bounds.\nBy looking at
non-extendable repetitions of power at least two (thus considering fracti
onal ones as well) Kolpakov and Kucherov tried to bound in ‘99 the numbe
r of runs in a word (non-necessarily 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\, all of these ideas have a common sticking poin
t\, namely the three squares lemma of Crochemore and Rytter\, which they a
ll use as main tool. In this talk I will present a different technique (wh
ich so far is not fully exploited) of trying to count distinct squares and
show some surprising connections between all of the above notions.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:M. Andrieu\, C. Cisterino\, L. Dvořáková\, Š. Holub\, F. Manea
\, C. Reutenauer
DTSTART:20210222T140000Z
DTEND:20210222T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/24
DESCRIPTION:Title: Day of short talks\nby M. Andrieu\, C. Cisterino\, L. Dv
ořáková\, Š. Holub\, F. Manea\, C. Reutenauer as part of One World Com
binatorics on Words Seminar\n\n\nAbstract\n15:00 Christophe Reutenauer An
arithmetical characterization of Christoffel words\n\n15:30 Célia Cistern
ino Two applications of the composition of a \n2-tape automaton and a weig
hted automaton\n\n16:00 Lubka Dvořáková On balanced sequences with the
minimal asymptotic critical exponent\n\n16:30 Štěpán Holub Formalizatio
n of Combinatorics on Words in Isabelle/HOL\n\n17:00 Florin Manea Efficien
tly Testing Simon's Congruence\n\n17:30 Mélodie Andrieu A Rauzy fractal u
nbounded in all directions of the plane\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Day of short talks
DTSTART:20210322T140000Z
DTEND:20210322T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/25
DESCRIPTION:Title: Day of short talks: I. Aedo\, F. Dolce\, A. Frid\, J. Palaci
o\, J. Shallit\nby Day of short talks as part of One World Combinatori
cs on Words Seminar\n\n\nAbstract\n15:00 Jane D. Palacio\, Coverable bi-in
finite substitution shifts\n\n15:30 Ibai Aedo\, On long arithmetic progres
sions in binary Morse-like words\n\n16:00 Francesco Dolce\, On morphisms p
reserving palindromic richness\n\n16:30 Jeffrey Shallit\, Robbins and Ardi
la meet Berstel\n\n17:00 Anna E. Frid\, The semigroup of trimmed morphisms
\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwenaël Richomme
DTSTART:20210503T130000Z
DTEND:20210503T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/26
DESCRIPTION:Title: On sets of indefinitely desubstitutable words\nby Gwena
ël Richomme as part of One World Combinatorics on Words Seminar\n\n\nAbst
ract\nThe stable set associated to a given set $S$ of nonerasing endomorph
isms or substitutions is the set of all right infinite words that can be i
ndefinitely desubstituted over $S$. This notion generalizes the notion of
sets of fixed points of morphisms. It is linked to $S$-adicity and to prop
erty preserving morphisms. Two main questions are considered. Which known
sets of infinite words are stable sets? Which ones are stable sets of a fi
nite set of substitutions? While bringing answers to the previous question
s\, some new way of characterizing several well-known sets of words such a
s the set of binary balanced words or the set of episturmian words are pre
sented. A characterization of the set of nonerasing endomorphisms that pre
serve episturmian words is also provided.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kevin Buzzard
DTSTART:20210510T130000Z
DTEND:20210510T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/27
DESCRIPTION:Title: Teaching computers to prove theorems\nby Kevin Buzzard a
s part of One World Combinatorics on Words Seminar\n\n\nAbstract\nOver the
last few years I have been teaching proofs of theorems to computers\, and
teaching students how to teach proofs of theorems to computers. The Krusk
al Katona theorem is a theorem I learnt as an MSc student\, and Cambridge
PhD student Bhavik Mehta taught it to the Lean theorem prover here: https:
//b-mehta.github.io/combinatorics/ . Lean's maths library `mathlib` https:
//github.com/leanprover-community/mathlib is now half a million lines of t
heorem proofs\, many of them proved by mathematicians who have picked up t
his language\, and most of them learnt it like Bhavik\, just choosing a pr
oject 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 teach
ing Lean is\, and where all this stuff might end up going. Rest assured --
I will not assume any prior familiarity with computer theorem provers in
this talk!\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeffrey Shallit
DTSTART:20210517T130000Z
DTEND:20210517T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/28
DESCRIPTION:Title: The Walnut Tutorial: Using A Tool for Doing Combinatorics o
n Words\nby Jeffrey Shallit as part of One World Combinatorics on Word
s Seminar\n\n\nAbstract\nWalnut is free open-source software\, written by
Hamoon Mousavi\, that can\nrigorously prove or disprove claims about autom
atic sequences (broadly\nunderstood)\, such as the Thue-Morse sequence\, t
he Fibonacci infinite\nword\, and others. It can also be used to create e
xplicit formulas for\nvarious aspects of such sequences\, such as subword
complexity\,\npalindrome complexity\, and so forth.\n\nIn this talk I won'
t discuss how it works. Instead I'll give a\ntutorial\, surveying the ki
nds of things you can and can't do with it.\nWe'll "get our hands dirty" a
nd solve problems in real time.\n\nAt the end\, if there's time\, I'll sol
icit problems about such sequences\nfrom the audience and try to solve the
m with Walnut. Come prepared with\nsome conjecture you haven't been able
to prove yet!\n\nThe tutorial will last about 90 minutes.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Etienne Moutot
DTSTART:20210531T130000Z
DTEND:20210531T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/29
DESCRIPTION:Title: Recent advances around Nivat's conjecture\nby Etienne Mo
utot as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nNi
vat's conjecture states that any two dimensional word with "low enough" pa
ttern complexity must be periodic.\nEven if the statement of the conjectur
e is quite simple and very similar to the one dimensional Morse-Hedlund th
eorem\, 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 s
tarted to use tools from symbolic dynamics to improve the bound required t
o prove periodicity. At about the same time\, Jarkko Kari and Michal Szaba
dos started to develop an algebraic approach to tackle the conjecture\, le
ading to very elegant proofs of new results related to Nivat's conjecture.
\n\nIn this talk I will present the conjecture and some of the last result
s around it. I will then focus on the algebraic approach initiated by Kari
and Szabados.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pascal Ochem
DTSTART:20210607T130000Z
DTEND:20210607T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/30
DESCRIPTION:Title: Avoiding large squares in trees and planar graphs\nby Pa
scal Ochem as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nThe 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 grap
h 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 classes:\n
$T(tree) = 4$\, $7 \\leq T(outerplanar) \\leq 12$\, $11 \\leq T(planar)
\\leq 768$.\nFollowing a suggestion of Grytczuk\, we consider the generali
sed parameters $T_k(C)$ such that only squares of period at least $k$\nmus
t 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 j
oint work with Daniel Gonçalves and Matthieu Rosenfeld.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Golnaz Badkobeh
DTSTART:20210614T130000Z
DTEND:20210614T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/31
DESCRIPTION:Title: Left Lyndon tree construction\nby Golnaz Badkobeh as par
t of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe extend the
left-to-right Lyndon factorisation of a word to the left Lyndon tree cons
truction of a Lyndon word. It yields an algorithm to sort the prefixes of
a Lyndon word according to the infinite ordering defined 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.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Florin Manea
DTSTART:20210628T130000Z
DTEND:20210628T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/32
DESCRIPTION:Title: Efficiently testing Simon's congruence\nby Florin Manea
as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn this
talk\, we will cover a series of recent algorithmic results related to th
e processing of subsequences occurring in words. Firstly\, we will show ho
w to test in linear time whether two given words have exactly the same set
of subsequences of length $k$ (or\, in other words\, whether 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\, f
or two given words\, which is the largest positive integer $k$ for which t
he two words are $k$-Simon-congruent. We will conclude this talk with a se
ries of related results. On the one hand\, we consider the problem of tran
sforming words by edit operations so that they become Simon-congruent and\
, on the other hand\, we consider the notion of absent subsequences in wor
ds and problems related to this.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Štěpán Holub
DTSTART:20210712T130000Z
DTEND:20210712T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/33
DESCRIPTION:Title: Using Isabelle/HOL in Combinatorics on Words research\nb
y Štěpán Holub as part of One World Combinatorics on Words Seminar\n\n\
nAbstract\nIn 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.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jason Bell
DTSTART:20210726T130000Z
DTEND:20210726T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/34
DESCRIPTION:Title: Lie complexity of words\nby Jason Bell as part of One Wo
rld Combinatorics on Words Seminar\n\n\nAbstract\nGiven a right-infinite w
ord $\\bf{w}$ over a finite alphabet\, we introduce a new complexity funct
ion $L_{\\bf w}(n)$\, motivated by the theory of Lie algebras\, whose valu
e at $n$ is the number of equivalence classes of factors $x$ of ${\\bf w}$
of length $n$ with the property that every cyclic permutation of $x$ is a
gain a factor of ${\\bf w}$\, where two words $x$ and $y$ are equivalent i
f there exist words $a$ and $b$ such that $x=ab$ and $y=ba$. We show that
the Lie complexity function is uniformly 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 consequence of these results we can show th
at if ${\\bf w}$ is a word of linear factor 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 every $n\\ge 1$. We also consider ext
ensions of these results. This is joint work with Jeffrey Shallit.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Day of Short Talks
DTSTART:20210621T130000Z
DTEND:20210621T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/35
DESCRIPTION:Title: Jakub Byszewski\, Jarosław Duda\, Jarkko Peltomäki\, Palak
Pandoh\, Clément Lagisquet\, Bartłomiej Pawlik\nby Day of Short Tal
ks as part of One World Combinatorics on Words Seminar\n\n\nAbstract\n15:0
0 Jakub Byszewski\, Automata and finite order automorphisms of the power s
eries ring\n\n15:30 Jarosław Duda\, Generalized Fibonacci coding problem
using Maximal Entropy Random Walk and Asymmetric Numeral Systems\n\n16:00
Jarkko Peltomäki\, Initial nonrepetitive complexity of regular episturmia
n words and their Diophantine exponents\n\n16:30 Palak Pandoh\, Counting s
cattered palindromes in a finite word\n\n17:00 Clément Lagisquet\, (LAMA)
On Markov Numbers: An answer to three conjectures from Aigner\n\n17:30 Ba
rtłomiej Pawlik\, Nonchalant procedure\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Arseny Shur
DTSTART:20210927T130000Z
DTEND:20210927T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/36
DESCRIPTION:Title: Abelian repetition threshold revisited\nby Arseny Shur a
s part of One World Combinatorics on Words Seminar\n\n\nAbstract\nAbelian
repetition threshold ART$(k)$ is the number separating fractional Abelian
powers which are avoidable and unavoidable over the $k$-letter alphabet. I
n contrast with the «usual» repetition threshold RT$(k)$\, no exact valu
es 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 conject
ured to be tight. We present a method of study of Abelian power-free langu
ages using random walks in prefix trees and some experimental results obta
ined 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.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:France Gheeraert
DTSTART:20211011T130000Z
DTEND:20211011T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/37
DESCRIPTION:Title: $S$-adic characterization of dendric languages: ternary case
\nby France Gheeraert as part of One World Combinatorics on Words Semi
nar\n\n\nAbstract\nUniformly recurrent dendric languages generalize Arnoux
-Rauzy languages and interval exchanges and are defined via the left-\, ri
ght- and biextensions of their words. In a series of articles\, Berthé et
al. introduced them and\, among other results\, proved that this family i
s stable under derivation\, which leads to the existence of particular $S$
-adic representations.\n\nIn this talk\, we will see how we can use the pr
operties of these representations to obtain an $S$-adic characterization o
f uniformly recurrent dendric languages. We give some general results then
focus on the case of a ternary alphabet to obtain a simpler characterizat
ion.\n\nThis is a joint work with Marie Lejeune and Julien Leroy.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fabien Durand
DTSTART:20211025T130000Z
DTEND:20211025T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/38
DESCRIPTION:Title: Beyond substitutive sequences : Self-induced dynamical syste
ms and sequences on compact alphabets\nby Fabien Durand as part of One
World Combinatorics on Words Seminar\n\n\nAbstract\nIt is well-known that
primitive substitutions are recognizable. This property implies that the
minimal substitution subshifts $(X\,S)$ are self-induced. That is\, there
exists a clopen set $U$ included in $X$ such that $(U\,S_U)$ is isomorphic
to $(X\,S)$\, where $S_U (x)=S^n (x)$ and $n>0$ is the first iterate comi
ng back to $U$.\n\nWe will see that all dynamical systems are self-induced
in a measurable perspective.\n\nBut from a topological point of view self
induction characterizes minimal substitution subshifts on possibly infini
te alphabets (even uncountable).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dan Rust
DTSTART:20211108T140000Z
DTEND:20211108T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/39
DESCRIPTION:Title: Random substitutions\nby Dan Rust as part of One World C
ombinatorics on Words Seminar\n\n\nAbstract\nA random substitution is a ge
neralisation of a substitution on a finite alphabet. Whereas with classica
l substitutions\, letters have a single word as an image\, random substitu
tions have a finite set of possible image words that are independently cho
sen 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 gives rise to languages of legal words tha
t share similar properties with substitutive words (i.e.\, hierarchical st
ructures) but which also have exponential complexity functions (entropy).
I will give an overview of this rarely explored class of systems\, some of
the aspects that have recently been studied\, and some easy-to-state open
problems.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Day of short talks
DTSTART:20211122T140000Z
DTEND:20211122T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/40
DESCRIPTION:Title: G. Kucherov\, J. O. Shallit\, J: Grytczuk\, D. Gabric\nb
y Day of short talks as part of One World Combinatorics on Words Seminar\n
\n\nAbstract\n15:00 Gregory Kucherov\, Minimizers and one question about d
e Bruijn graphs\n15:30 Jeffrey O. Shallit\, Abelian cubes and additive cub
es in the Tribonacci word\n15:45 Jarosław Grytczuk\, Twins in permutation
s\n16:15 Daniel Gabric\, Words that almost commute\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gabriele Fici
DTSTART:20211206T140000Z
DTEND:20211206T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/41
DESCRIPTION:Title: Some Remarks on Automatic Sequences\, Toeplitz words and Per
fect Shuffling\nby Gabriele Fici as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nOne of the many nice properties of the Thue-
Morse sequence $t = 0110100110010110\\cdots$ is that t is equal to the per
fect shuffling of itself with its binary complement $(1-t)$\, i.e.\, it ca
n be defined by means 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’$ a
nd $w’’$ the even and the odd part of $w$\, respectively. We will exhi
bit some curious facts about this decomposition for some (more or less) kn
own 2- and 3-automatic sequences.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jakub Konieczny
DTSTART:20211220T140000Z
DTEND:20211220T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/42
DESCRIPTION:Title: Finitely-valued generalised polynomials\nby Jakub Koniec
zny as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nGen
eralised polynomials are expressions constructed from polynomials with the
use of the floor function\, addition and multiplication\, such as $\\lflo
or \\sqrt{2} n \\lfloor \\sqrt{3} n^2\\rfloor + \\sqrt{6} + \\frac{1}{2}\\
rfloor$. Despite superficial similarity\, generalised polynomials exhibit
many phenomena which are impossible for ordinary polynomials. In particula
r\, there exist generalised polynomial sequences which take only finitely
many values but are not constant. This is the case\, for instance\, for St
urmian sequences.\n\nIn my talk\, I will discuss finitely-valued generalis
ed polynomial sequences from the perspective of combinatorics on words. Th
e talk will include a survey of existing results on generalised polynomial
s\, adapted to the current context\, as well as several new results obtain
ed in joint works with Boris Adamczewski and with Jakub Byszewski.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lubomíra Dvořáková
DTSTART:20220110T140000Z
DTEND:20220110T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/43
DESCRIPTION:Title: On minimal critical exponent of balanced sequences\nby L
ubomíra Dvořáková as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nThe conjecture stated by Rampersad\, Shallit and Vandomme s
ays that the minimal critical exponent of balanced sequences over the alph
abet 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 mor
e details the ideas and the techniques used to refute this conjecture by s
howing that the picture is different for bigger alphabets. We prove that c
ritical exponents of balanced sequences over an alphabet of size $d>10$ a
re lower bounded by $(d-1)/(d-2)$ and this bound is attained for all even
numbers $d>10$. \n\nAccording to this result\, we conjecture that the leas
t critical exponent of a balanced sequence over $d$ letters is $(d-1)/(d-2
)$ for all $d>10$.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Markus Whiteland
DTSTART:20220124T140000Z
DTEND:20220124T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/44
DESCRIPTION:Title: On some decidable properties of discrete-time linear dynamic
al systems\nby Markus Whiteland as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nA discrete-time linear dynamical system (LDS)
$(A\,x)$ is the orbit of a point $x \\in \\mathbb{R}^d$ under a linear ma
p $A\\colon \\mathbb{R}^d \\to \\mathbb{R}^d$. In this talk we consider de
cision problems on LDS arising from program verification\, such as reachab
ility problems: given 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 su
ch questions quickly lead to open problems\, such as Skolem's problem on l
inear recurrence sequences. We identify the borderline between hard instan
ces and decidable instances with respect to the dimension of the target se
t $T$. The methods used in the decidable cases quickly give rise to symbol
ic dynamical systems over which we have a lot of control: this allows us t
o go beyond mere reachability to deciding $\\omega$-regular properties of
the LDS with respect to a low-dimensional target set $T$.\n\nJoint work wi
th C. Baier\, F. Funke\, S. Jantsch\, T. Karimov\, E. Lefaucheux\, F. Luca
\, J. Ouaknine\, D. Purser\, A. Varonka\, and J. Worrell.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Dekking
DTSTART:20220207T140000Z
DTEND:20220207T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/45
DESCRIPTION:Title: Combinatorics of Fibonacci and golden mean number representa
tions\nby Michel Dekking as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nHow many ways are there to represent a number as a s
um of powers 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 Fibonacc
i numbers?\n\nI will give some answers to these questions in my talk.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean-Paul Allouche
DTSTART:20220307T140000Z
DTEND:20220307T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/46
DESCRIPTION:Title: Thue and 7-3\nby Jean-Paul Allouche as part of One World
Combinatorics on Words Seminar\n\n\nAbstract\nMarch 7\, 2022 (in French 7
/3) is the 100th anniversary of the death of Axel Thue. He was a Norwegian
mathematician\, principally known for his work in Diophantine approximati
on\, but he is also known for his work in combinatorics.\n\nWe will speak
a little of his number-theoretic papers\, and more about his contribution
in combinatorics\, essentially restricting ourselves to the –ubiquitous
– Thue-Morse or Prouhet-Thue-Morse sequence. We will try to survey not o
nly some well-known features of this sequence\, but also less classical pr
operties: one of these is an occurrence of… 7/3 for this sequence\, the
other is about Shogi (将棋)\, or Japanese chess\, and the Sennichite (
千日手) (a new rule decided after a play dated March… 8\, 1983).\n\nT
o conclude this abstract\, we do not resist to give a quote of Thue: “Th
e further removed from usefulness or practical application\, the more impo
rtant.” Removed from practical application? one might want to look at th
e definition of the programming language “Thue” that Wikipedia describ
es as follows: “Thue is an esoteric programming language invented by Joh
n Colagioia in early 2000. It is a meta-language that can be used to defin
e or recognize Type-0 languages from the Chomsky hierarchy. Because it is
able to define languages of such complexity\, it is also Turing-complete i
tself. Thue is based on a nondeterministic string rewriting system called
semi-Thue grammar\, which itself is named after the Norwegian mathematicia
n Axel Thue.”\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Narad Rampersad
DTSTART:20220321T130000Z
DTEND:20220321T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/47
DESCRIPTION:Title: Applications of Walnut to problems of local periodicity\
nby Narad Rampersad as part of One World Combinatorics on Words Seminar\n\
n\nAbstract\nThere are a number of natural choices for measuring the local
\nperiodicity at a given position $i$ of an infinite word: for instance\,\
none could consider repetitions 1) ending at position $i$\; 2) starting\na
t position $i$\; or 3) centered at position $i$. With regards to\noption
1)\, it is known that aperiodic infinite words cannot have all\nsufficient
ly large prefixes end with cubes. It is natural then to ask\nfor such wor
ds how many prefixes can end with cubes. Using Walnut\, we\nobtain a char
acterization 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 asympto
tic behaviour of this function for some\n2-automatic sequences\, such as t
he Thue-Morse sequence\, the\nRudin-Shapiro sequence\, and the period-doub
ling sequence.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Etienne Moutot
DTSTART:20220221T140000Z
DTEND:20220221T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/48
DESCRIPTION:Title: Pattern complexity of 2D substitutive shifts\nby Etienne
Moutot as part of One World Combinatorics on Words Seminar\n\n\nAbstract\
nIn this presentation\, I will talk about pattern complexity of two-dimens
ional substitutive shifts. More precisely\, I will focus on lower bounds o
n the complexity of {\\bf aperiodic} 2D substitutive shifts.\n\n{\\it Patt
ern complexity} consists in counting the number of different mxn rectangul
ar 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 co
njecture [1] shows that any aperiodic subshift have pattern complexity at
least $mn+1$ for all $m$ and $n$.\n\nWith Coline Petit-Jean we have been t
rying to improve this lower bound for a particular class of shift spaces:
substitutive shifts. For some substitutions ({\\it primitive} and {\\it ma
rked} substitutions)\, we show that if their shift space is aperiodic\, th
en it has complexity at least $C*mn$\, with $C>1$ a constant depending on
the substitution. 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 similar result might still hold.\n\n[1] Decidability and Periodicity of
Low Complexity Tilings. Jarkko Kari\, Etienne Moutot\, Theory of Computin
g Systems\, 2021\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Moussa Barro
DTSTART:20220516T130000Z
DTEND:20220516T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/49
DESCRIPTION:Title: Billard dans le cube\nby Moussa Barro as part of One Wor
ld Combinatorics on Words Seminar\n\n\nAbstract\nOn considère le billard
dans un cube. On code une trajectoire par les faces rencontrées. Le but d
e l'exposé sera de décrire le langage d'un tel mot dans le cas ou l'orbi
te n'est pas dense.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Colin Defant
DTSTART:20220404T130000Z
DTEND:20220404T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/50
DESCRIPTION:Title: Anti-powers in Aperiodic Recurrent Words\nby Colin Defan
t as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn 20
16\, Fici\, Restivo\, Silva\, and Zamboni introduced the notion of a $k$-a
nti-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 distinct. I will beg
in by reviewing the main results that these authors proved about anti-powe
rs. I will then discuss anti-powers appearing as factors in the Thue-Morse
word. This will lead into a discussion of anti-powers in aperiodic recurr
ent words and aperiodic morphic words.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christophe Reutenauer
DTSTART:20220425T130000Z
DTEND:20220425T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/51
DESCRIPTION:Title: Constructions and parametrization of conjugates of Christoff
el words\nby Christophe Reutenauer as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nFollowing a recent work of Michel Laurent
and the first author\, we propose a deformation of the Rauzy rules (equiva
lently of the de Luca construction of standard words) in order to construc
t all conjugates of all Christoffel words (equivalently of all standard wo
rds). This construction is based on integer legal Ostrowski representation
s\, following Frid. The constructed word depends only the represented inte
ger (and even works in the free group\, up to conjugation however). Choosi
ng greedy representations\, we determine of the longest border of conjugat
es\, thereby recovering results of Lapointe on the smallest periods. Choos
ing the lazy representation\, we may revisit the Sturmian graph of Epifani
o\, Frougny\, Gabriele\, Mignosi and Shallit\; in particular we show that
this graph is essentially a subgraph of the Stern-Brocot tree\, and that t
he compact graph (which is a compaction of the minimal automaton of the se
t of suffixes of a central word) is similarly embedded in the tree of cent
ral words of Aldo de Luca.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre-Adrien Tahay
DTSTART:20220530T130000Z
DTEND:20220530T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/52
DESCRIPTION:Title: Column representation of words in cellular automata\nby
Pierre-Adrien Tahay as part of One World Combinatorics on Words Seminar\n\
n\nAbstract\nThe task of representing a sequence over a finite alphabet in
the space-time\ndiagram of a cellular automaton is a non-trivial and stil
l not entirely explored\ntopic. One of the first results on the subject wa
s done by Fischer in 1965 with a construction of the characteristic sequen
ce of primes numbers. Many results and improvements have been established
since. In 2015\, Rowland and Yassawi showed that there is a close connecti
on between the $p$-automatic sequences and the linear cellular automata. M
ore precisly the columns of linear cellular automata are $p$-\nautomatic s
equences and all $p$-automatic sequences can be realized by some linear ce
llular automata with memory. Moreover their proof is constructive. In 2018
\, Marcovici\, Stoll and Tahay investigated some constructions for nonauto
matic sequences such as the characteristic sequences of polynomials and th
e Fibonacci word.\n\nIn this talk I will present recent results obtained i
n collaboration with Francesco Dolce where we generalized the construction
for the Fibonacci word in a column of a cellular automaton\, to any Sturm
ian word with quadratic slope. Our proof is constructive and use the ultim
ate periodicity of the continued fraction expansion of the slope of the wo
rd.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kristina Ago and Bojan Bašić
DTSTART:20220613T130000Z
DTEND:20220613T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/53
DESCRIPTION:Title: Some recent results on two "palindromicity" measures\nby
Kristina Ago and Bojan Bašić as part of One World Combinatorics on Word
s Seminar\n\n\nAbstract\nVarious measures of the degree of "palindromicity
" of a given word have been defined in the literature. In this talk we pre
sent some of our results concerning two such measures. The first one is th
e so-called \\emph{palindromic defect} (or only \\emph{defect}). Let $|\\m
athrm{Pal}(w)|$ denote the number of palindromic factors of a word $w$. Th
e palindromic defect of $w$ is defined by $|w|+1-|\\mathrm{Pal}(w)|$ (it c
an be proved that this value is always nonnegative). This definition can b
e naturally extended to infinite words. While infinite words whose defect
is zero (called \\emph{rich}) have been researched quite much\, there are
noticeably less results in the literature on infinite words of finite posi
tive defect. In the first part of the talk we introduce a construction of
an infinite family of infinite words whose defect is finite and in many ca
ses positive (with fully characterized cases when the defect is $0$)\, and
we analyze their properties. Each of those words is either periodic (whic
h is a less interesting case\, and explicitly characterized)\, or recurren
t but not uniformly recurrent. Examples of explicit constructions of such
words that are not uniformly recurrent have been quite deficient in the li
terature so far.\n\nThe second part of talk is devoted to the so-called \\
emph{MP-ratio}. The concept of MP-ratio is based on palindromic subwords (
and not factors) of a given finite word. Call a word over an $n$-ary alpha
bet \\emph{minimal-palindromic} if it does not contain palindromic subword
s of length greater than $\\big\\lceil\\frac{|w|}n\\big\\rceil$. The \\emp
h{MP-ratio} of a given $n$-ary word $w$ is defined as the quotient $\\frac
{|rws|}{|w|}$\, where $r$ and $s$ are words such that the word $rws$ is mi
nimal-palindromic and that the length $|r|+|s|$ is minimal possible. In or
der for the MP-ratio to be well-defined\, it has to be shown that such a p
air $(r\,s)$ always exist. It has been known for some time that this is tr
ue in the binary case\, but this question becomes much more complicated fo
r larger arities. In this talk we show that the MP-ratio is well-defined f
or any arity\, and we present some further results on this topic.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Antoine Domenech
DTSTART:20220620T130000Z
DTEND:20220620T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/54
DESCRIPTION:Title: Avoiding doubled patterns\nby Antoine Domenech as part o
f One World Combinatorics on Words Seminar\n\n\nAbstract\nA pattern $P$ is
$k$-avoidable if there exists\nan infinite word over $k$ letters that con
tains no occurrence of $P$.\nA pattern is doubled if all its variables app
ear at least twice.\nIt is known that doubled patterns are 3-avoidable and
it is conjectured\nthat only a finite number of doubled patterns are not
2-avoidable.\nWe show that square-free doubled patterns with at most 4 var
iables are 2-avoidable.\nThen\, for each pattern doubled $P$ with at most
3 variables that is\nnot 2-avoidable\, we determine the minimum number of
distinct\noccurrences of $P$ that are contained in an infinite binary word
.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre Popoli
DTSTART:20220627T130000Z
DTEND:20220627T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/55
DESCRIPTION:Title: Maximum order complexity for some automatic and morphic sequ
ences along polynomial values\nby Pierre Popoli as part of One World C
ombinatorics on Words Seminar\n\n\nAbstract\nAutomatic sequences are not s
uitable sequences for cryptographic\napplications since both their subword
complexity and their expansion\ncomplexity are small\, and their correlat
ion measure of order 2 is\nlarge. These sequences are highly predictable d
espite having a large\nmaximum order complexity. However\, recent results
show that polynomial\nsubsequences of automatic sequences\, such as the Th
ue-Morse sequence\nor the Rudin-Shapiro sequence\, are better candidates f
or pseudorandom\nsequences. A natural generalization of automatic sequence
s are morphic\nsequences\, given by a fixed point of a prolongeable morphi
sm that is\nnot necessarily uniform. In this talk\, I will present my resu
lts on\nlowers bounds for the maximum order complexity of the Thue-Morse\n
sequence\, the Rudin-Shapiro sequence and the sum of digits function in\nZ
eckendorf base\, which are respectively automatics and morphic\nsequences.
\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zachary Chase
DTSTART:20220711T130000Z
DTEND:20220711T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/56
DESCRIPTION:Title: The separating words\, $k$-deck\, and trace reconstruction p
roblems\nby Zachary Chase as part of One World Combinatorics on Words
Seminar\n\n\nAbstract\nWhat is the smallest size of a DFA that can separat
e two\ngiven strings of length $n$? Can two distinct strings of length $n$
have\nthe same multiset of subsequences of length $n^{1/3}$? How many ran
dom\nsubsequences of length $n/2$ of an unknown string $x$ of length $n$ d
o you\nneed to determine $x$ with high probability? We discuss these three
\nproblems\, each having an exponential gap between the best known upper\n
and lower bounds\, and touch upon how they might be more related than\none
might expect.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shuo Li
DTSTART:20220919T130000Z
DTEND:20220919T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/57
DESCRIPTION:Title: On the number of squares in a finite word\nby Shuo Li as
part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA conject
ure of Fraenkel and Simpson states that the number of distinct squares in
a finite word $w$\n is bounded by its length. In this talk\, we will revie
w this conjecture from the perspective of the topological properties of th
e Rauzy graphs of $w$. We prove this conjecture by giving a stronger state
ment: the number of distinct squares in a finite word \n$w$ is bounded by
the length of $w$ minus the number of distinct letters in $w$.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/57/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robbert Fokkink
DTSTART:20221003T130000Z
DTEND:20221003T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/58
DESCRIPTION:Title: A few words on games\nby Robbert Fokkink as part of One
World Combinatorics on Words Seminar\n\n\nAbstract\nAn impartial combinato
rial game involves a set of positions that are either won or lost for the
player that moves next. These are the so-called N-positions. If you know t
he set of N-positions\, then you have solved the game. Members of our comm
unity will immediately wonder if the characteristic sequence of the set of
N-positions form a word. It turns out that Fibonacci word gives the set o
f N-positions in Wythoff Nim. Eric Duchene and Michel Rigo found other exa
mples of impartial games that are given by words\, initiating ongoing work
on the link between words and games. In this talk I will show how a modif
ication of Wythoff Nim can be described by the Tribonacci word. This is jo
int work with Dan Rust and Cisco Ortega.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/58/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Giuseppe Romana
DTSTART:20221017T130000Z
DTEND:20221017T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/59
DESCRIPTION:Title: String Attractor: a Combinatorial object from Data Compressi
on\nby Giuseppe Romana as part of One World Combinatorics on Words Sem
inar\n\n\nAbstract\nVery recently\, Kempa and Prezza [STOC 2018] introduce
d the notion of String Attractor in the field of Data Compression\, and sh
owed how this concept was already implicit in many other well known compre
ssion schemes.\nBasically\, a String Attractor $\\Gamma$ of a finite word
$w$ is a set of positions in $w$ such that each distinct factors that occu
rs in $w$ has at least an occurrence that crosses a position $j \\in \\Gam
ma$. \nIn this talk\, we explore String Attractors from a combinatorial pe
rspective.\nWe discuss how the size $\\gamma^*$ of a string attractor of m
inimum size is affected when some classical combinatorial operations are a
pplied to finite words.\nFurther\, we show how the size and other structur
al properties of string attractors can be used to obtain new characterizat
ions for infinite words.\nMost of the results presented in this talk come
from [A combinatorial view on string attractors\, Theoret. Comput. Sci. 20
21] and [String Attractors and Infinite Words\, LATIN 2022] (to appear).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/59/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Krenn
DTSTART:20221107T140000Z
DTEND:20221107T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/60
DESCRIPTION:Title: $q$-Recursive Sequences and their Asymptotic Analysis\nb
y Daniel Krenn as part of One World Combinatorics on Words Seminar\n\n\nAb
stract\nIn this talk\, we consider Stern’s diatomic sequence\, the numbe
r of\nnon-zero elements in some generalized Pascal's triangle and the numb
er\nof unbordered factors in the Thue-Morse sequence as running examples.\
nAll these sequences can be defined recursively and lead to the concept\no
f so-called $q$-recursive sequences. Here $q$ is an integer and at least $
2$\,\nand $q$-recursive sequences are sequences which satisfy a specific t
ype of\nrecurrence relation: Roughly speaking\, every subsequence whose in
dices\nrun through a residue class modulo $q^M$ is a linear combination of
\nsubsequences where for each of these subsequences\, the indices run\nthr
ough a residue class modulo $q^m$ for some $m < M$.\n\nIt turns out that t
his property is quite natural and many combinatorial\nsequences are in fac
t $q$-recursive. We will see that $q$-recursive\nsequences are related to
$q$-regular sequences and a $q$-linear\nrepresentation of a sequence can b
e computed easily. Our main focus is the asymptotic\nbehavior of the summa
tory functions of $q$-recursive sequences. Beside\ngeneral results\, we pr
esent a precise asymptotic analysis of our three examples. For the first t
wo sequences\, our analysis even leads to\nprecise formulae without error
terms.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/60/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sebastián Barbieri
DTSTART:20221121T140000Z
DTEND:20221121T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/61
DESCRIPTION:Title: Indistinguishable asymptotic pairs\nby Sebastián Barbie
ri as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe s
ay two bi-infinite words are asymptotic if they differ in finitely many co
ordinates. We say they are indistinguishable if for any finite word w\, th
e number of occurrences of w that intersect the set of differences in each
of them is the same. In this talk we will study these objects and show th
at they are very closely related to Sturmian configurations. We will also
show that a higher-dimensional analogue of the theorem holds\, and as an a
pplication of this result we will provide a formula for computing the comp
lexity of a multidimensional Sturmian configuration on any finite connecte
d support. This is joint work with S. Labbé.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/61/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Josef Rukavicka
DTSTART:20221205T140000Z
DTEND:20221205T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/62
DESCRIPTION:Title: Palindromic factorization of rich words\nby Josef Rukavi
cka as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA f
inite word $w$ is called rich if it contains $\\vert w\\vert+1$ distinct p
alindromic factors including the empty word. For every finite rich word $w
$ there are distinct nonempty palindromes $w_1\, w_2\,\\dots\,w_p$ such th
at $w=w_pw_{p-1}\\cdots w_1$ and $w_i$ is the longest palindromic suffix o
f $w_pw_{p-1}\\cdots w_i$\, where $1\\leq i\\leq p$. This palindromic fact
orization 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=\\vert w\\vert$ then $l
uf(w)\\leq c\\frac{n}{\\ln{n}}$.\nWe improve this result as follows: There
are constants $\\mu\, \\pi$ such that if $w$ is a finite 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 alp
habet.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/62/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jason Bell
DTSTART:20221219T140000Z
DTEND:20221219T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/63
DESCRIPTION:Title: Noncommutative rational Pólya series\nby Jason Bell as
part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA Pólya s
eries over a field $K$ is a formal noncommutative power series whose nonze
ro coefficients are contained in a finitely generated subgroup of the mult
iplicative group of $K$. A complete description of such one-variable serie
s was given by Pólya\, and an extension to general noncommutative rationa
l series in terms of unambiguous weight automaton was later conjectured by
Reutenauer. We explain how to prove Reutenauer’s conjecture and discus
s certain decidability aspects of our work. This is joint work with Danie
l Smertnig.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/63/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pamela Fleischmann
DTSTART:20230109T140000Z
DTEND:20230109T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/64
DESCRIPTION:Title: $m$-Nearly $k$-Universal Words - Investigating Simon Congru
ence\nby Pamela Fleischmann as part of One World Combinatorics on Word
s Seminar\n\n\nAbstract\nDetermining the index of the Simon congruence is
a long outstanding open problem. Two words $u$ and $v$ are called Simon co
ngruent if they have the same set of scattered factors\, which are parts o
f the word in the correct order but not necessarily consecutive\, e.g.\, o
ath is a scattered factor of logarithm. Following the idea of scattered fa
ctor $k$-universality\, we investigate $m$-nearly $k$-universality\, i.e.\
, words where $m$ scattered factors of length $k$ are absent\, w.r.t. Simo
n congruence. We present a full characterisation as well as the index of t
he congruence for $m = 1$\, $2$\, and $3$. Moreover\, we present a charact
erisation of the universality of repetitions.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/64/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Natalie Behague
DTSTART:20221024T130000Z
DTEND:20221024T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/65
DESCRIPTION:Title: Synchronizing Times for $k$-sets in Automata\nby Natalie
Behague as part of One World Combinatorics on Words Seminar\n\n\nAbstract
\nAn automaton consists of a finite set of states and a collection of func
tions from the set of states to itself. An automaton is synchronizing if t
here is a word (that is\, a sequence of functions) that maps all states on
to the same state. Černý’s conjecture on the length of the shortest su
ch word is one of the most famous open problem in automata theory. We cons
idered the closely related question of determining the minimum length of a
word that maps some k states onto a single state.\n\nFor synchronizing au
tomata\, 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 single state.
We further improved the upper bound on the minimum length of a word sendi
ng 4 states to a singleton from $0.5n^2$ to $≈ 0.459n^2$\, and the minim
um length sending 5 states to a singleton from $n^2$ to $≈ 0.798n^2$. I
will discuss this result and some open questions.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/65/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lubomíra Dvořáková
DTSTART:20230123T140000Z
DTEND:20230123T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/66
DESCRIPTION:Title: Essential difference between the repetitive thereshold and a
symptotic repetitive threshold of balanced sequences\nby Lubomíra Dvo
řáková as part of One World Combinatorics on Words Seminar\n\n\nAbstrac
t\nAt first\, we will summarize both the history and the state of the art
of the critical exponent and the asymptotic critical exponent of balanced
sequences. \nSecond\, we will colour the Fibonacci sequence by suitable co
nstant gap sequences to provide an upper bound on the asymptotic repetitiv
e threshold of $d$-ary balanced sequences. The bound is attained for $d$ e
qual to $2$\, $4$ and $8$ and we conjecture that it happens for infinitely
many even $d$'s. \nFinally\, we will reveal an essential difference in b
ehavior of the repetitive threshold and the asymptotic repetitive thresho
ld of balanced sequences: The repetitive threshold of $d$-ary balanced se
quences is known to be at least $1+1/(d-2)$ for each $d$ larger than two.
In contrast\, our bound implies that the asymptotic repetitive threshold
of $d$-ary balanced sequences is at most $1+\\phi^3/2^{d-3}$ for each $d$
larger than one\, where $\\phi$ is the golden mean. \n\nJoint work with E
dita Pelantová.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/66/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aline Parreau and Eric Duchêne
DTSTART:20230227T140000Z
DTEND:20230227T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/67
DESCRIPTION:Title: Taking and merging games as rewrite games\nby Aline Parr
eau and Eric Duchêne as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nIn this talk\, we present some of the links between combina
torial games and language theory. A combinatorial game is a 2-player game
with no chance and with perfect information. Amongst them\, the family of
heap games such as the game of Nim\, subtraction or octal games belong to
the the most studied ones. Generally\, the analysis of such games consist
in determining which player has a winning strategy. We will first see how
this question is investigated in the case of heap games.\n\nIn a second pa
rt of the talk\, we will present a generalization of heap games as rewrite
games on words. This model was introduced by Waldmann in 2002. Given a fi
nite alphabet and a set of rewriting rules on it\, starting from a finite
word w\, each player alternately applies a rule on w. The first player una
ble to apply a rule loses the game. In this context\, the main question is
now about the class of the language formed by the losing and winning posi
tions of the game. For example\, for octal games that are solved in polyno
mial time\, the losing positions form a rational language. By using the mo
del of rewrite games\, we will investigate here a new family of heap games
that consist in merging heaps of tokens\, and consider some of the differ
ent classes of languages that may emerge according to the rules of the gam
e.\n\nJoint work with V. Marsault and M. Rigo.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/67/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Konefal
DTSTART:20230206T140000Z
DTEND:20230206T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/68
DESCRIPTION:Title: Examining the Class of Formal Languages which are Expressibl
e via Word Equations\nby Matthew Konefal as part of One World Combinat
orics on Words Seminar\n\n\nAbstract\nA word equation can be said to expre
ss a formal language via each variable occurring in it. The class WE of fo
rmal languages which can be expressed in this way is not well understood.
I will discuss a number of necessary and sufficient conditions for a form
al 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.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/68/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Léo Poirier and Wolfgang Steiner
DTSTART:20230306T140000Z
DTEND:20230306T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/69
DESCRIPTION:Title: Factor-balanced S -adic languages\nby Léo Poirier and
Wolfgang Steiner as part of One World Combinatorics on Words Seminar\n\n\n
Abstract\nLéo Poirier and Wolfgang Steiner Factor-balanced \nS\n-adic lan
guages\n\nA set of words\, also called a language\, is letter-balanced if
the number of occurrences of each letter only depends on the length of the
word\, up to a constant. Similarly\, a language is factor-balanced if the
difference of the number of occurrences of any given factor in words of t
he same length is bounded. The most prominent example of a letter-balanced
but not factor-balanced language is given by the Thue-Morse sequence. We
establish connections between the two notions\, in particular for language
s given by substitutions and\, more generally\, by sequences of substituti
ons. We show that the two notions essentially coincide when the sequence o
f substitutions is proper. For the example of Thue-Morse-Sturmian language
s\, we give a full characterisation of factor-balancedness.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/69/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Štěpán Starosta
DTSTART:20230327T130000Z
DTEND:20230327T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/70
DESCRIPTION:Title: On a faithful representation of Sturmian morphisms\nby
Štěpán Starosta as part of One World Combinatorics on Words Seminar\n\n
\nAbstract\nThe set of morphisms mapping any Sturmian sequence to a Sturmi
an sequence forms together with composition the so-called monoid of Sturm.
For this monoid\, we define a faithful representation by $(3\\times 3)$-
matrices with integer entries. We find three convex cones in $\\mathbb{R}^
3$ and show that a matrix $R \\in Sl(\\mathbb{Z}\,3)$ is a matrix represe
nting a Sturmian morphism if the three cones are invariant under multipli
cation by $R$ or $R^{-1}$. This property offers a new tool to study Sturmi
an sequences. We provide\nalternative proofs of four known results on Stur
mian sequences fixed by a primitive morphism and a new result concerning t
he square root of a Sturmian sequence.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/70/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeffrey Shallit
DTSTART:20230403T130000Z
DTEND:20230403T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/71
DESCRIPTION:Title: New Results in Additive Number Theory via Combinatorics on W
ords\nby Jeffrey Shallit as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nAdditive number theory is the study of the additive
properties of integers.\nSurprisingly\, we can use techniques from combina
torics on words to prove\nresults in this area.\nIn this talk I will discu
ss the number of representations of an integer N as\na sum of elements fro
m some famous sets\, such as the evil numbers\, the\nodious\nnumbers\, the
Rudin-Shapiro numbers\, Wythoff sequences\, etc.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/71/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthieu Rosenfeld
DTSTART:20230522T130000Z
DTEND:20230522T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/73
DESCRIPTION:by Matthieu Rosenfeld as part of One World Combinatorics on Wo
rds Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/73/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mélodie Lapointe
DTSTART:20230508T130000Z
DTEND:20230508T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/74
DESCRIPTION:Title: Perfectly clustering words: Induction and morphisms\nby
Mélodie Lapointe as part of One World Combinatorics on Words Seminar\n\n\
nAbstract\nPerfectly 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.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/74/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Craig Kaplan
DTSTART:20230515T130000Z
DTEND:20230515T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/75
DESCRIPTION:Title: An aperiodic monotile\nby Craig Kaplan as part of One Wo
rld Combinatorics on Words Seminar\n\n\nAbstract\nA set of shapes is calle
d aperiodic if the shapes admit tilings of \n the plane\, but none that ha
ve translational symmetry. A longstanding\n open problem asks whether a s
et consisting of a single shape could \n be aperiodic\; such a shape is kn
own as an aperiodic monotile or \n sometimes an "einstein". The recently
discovered "hat" monotile\n settles this problem in two dimensions. In th
is talk I provide\n necessary background on aperiodicity and related topic
s in tiling\n theory\, review the history of the search for for an aperiod
ic \n monotile\, and then discuss the hat and its mathematical properties.
\n\nFull disclosure: this is the same title and abstract that I just sent
to Kevin Hare for the Numeration seminar the week before (May 9th). I exp
ect that the talks will be largely the same\, but if I have a chance to in
corporate any connections to combinatorics on words into my talk for you\,
I will.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/75/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bastián Espinoza
DTSTART:20230912T130000Z
DTEND:20230912T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/76
DESCRIPTION:Title: An S -adic characterization of linear-growth complexity sub
shifts\nby Bastián Espinoza as part of One World Combinatorics on Wor
ds Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/76/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Svetlana Puzynina
DTSTART:20231107T140000Z
DTEND:20231107T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/77
DESCRIPTION:Title: Well distributed occurrences property in infinite words\
nby Svetlana Puzynina as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nWe say that an infinite word $u$ on a $d$-ary alphabet has
the well distributed occurrences property if\, for each factor $w$ of $u$
\, each positive integer $m$\, and each vector $v\\in {\\mathbb Z}_m^d$\,
there is an occurrence of $w$ such that the Parikh vector of the prefix of
$u$ preceding such occurrence is congruent to $v$ modulo $m$. In this tal
k we will discuss how aperiodic infinite words with well distributed occur
rences can be used to produce aperiodic pseudorandom number generators wit
h good statistical behavior. We study the well distributed occurrences pro
perty for certain families of infinite words including words generated by
morphisms\, Sturmian words and Arnoux–Rauzy words. The talk is based on
new and old results.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/77/
END:VEVENT
BEGIN:VEVENT
SUMMARY:James Currie
DTSTART:20230926T130000Z
DTEND:20230926T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/78
DESCRIPTION:Title: The analogs of overlap-freeness for the period-doubling morp
hism and for the Fibonacci morphism\nby James Currie as part of One Wo
rld Combinatorics on Words Seminar\n\n\nAbstract\nThe Thue-Morse morphism
is the binary map $\\mu: 0 \\to 01\, 1 \\to 10$. A word $w$ is\noverlap-fr
ee if it has no factor of the form $xyxyx$\, where $x$ is\nnon-empty. A de
ep connection between these two concepts is the engine\nbehind several res
ults:\n\n- The precise characterization of finite prefixes of infi
nite\noverlap-free binary words (Fife’s Theorem)\;\n\n- A precis
e enumeration of overlap-free binary words\;\n\n- A characterizati
on of all binary patterns encountered by the\nThue-Morse word\;\n\n-
The determination of the lexicographically least infinite\noverlap-free
word.\n\nGiven another morphism\, is there an analog of overlap-freeness
which\nfacilitates the proof of similar results? We show that the answer i
s\nyes for the period doubling morphism $\\delta :0 \\to 01\, 1\\to 00$\,
and for the\nFibonacci morphism $\\varphi: 0\\to 01\, 1\\to 0$.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/78/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ľubomíra Dvořáková
DTSTART:20231010T130000Z
DTEND:20231010T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/79
DESCRIPTION:Title: String attractors and pseudopalindromic closures\nby Ľu
bomíra Dvořáková as part of One World Combinatorics on Words Seminar\n
\n\nAbstract\nIn this contribution we carry on a study of string attractor
s of important classes of sequences. Attractors of minimum size of factors
/prefixes/particular prefixes of the following sequences have been determi
ned so far: Sturmian sequences (Mantaci\, Restivo\, Romana\, Rosone\, Scio
rtino\, 2021\, Dvořáková\, 2022)\, episturmian sequences (Dvořáková\
, 2022)\, the Tribonacci sequence (Schaeffer and Shallit\, 2021)\, the Thu
e-Morse sequence (Kutsukake\, 2020\, Schaeffer and Shallit\, 2021\, Dolce\
, 2023)\, the period-doubling sequence (Schaeffer and Shallit\, 2021)\, th
e powers of two sequence (Schaeffer and Shallit\, 2021\, Kociumaka\, Navar
ro\, Prezza\, 2021)\, complementary-symmetric Rote sequences (Dvořáková
and Hendrychová\, 2023). Recently\, string attractors in fixed points of
k-bonacci-like morphisms have been described (Gheeraert\, Romana\, Stipul
anti\, 2023).\n\nIn our talk we aim to present the following results: Usin
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. Observing usef
ullness of palindromic closures when dealing with attractors\, we turned o
ur attention to pseudopalindromic prefixes of the so-called binary general
ized pseudostandard sequences. We determined the minimum size attractors i
n two cases: for pseudostandard sequences obtained when iterating uniquely
the antipalindromic closure (the minimum size is three) and for the compl
ementary-symmetric Rote sequences when iterating both palindromic and anti
palindromic closure (the minimum size is two).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/79/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Herman Goulet-Ouellet
DTSTART:20231024T130000Z
DTEND:20231024T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/80
DESCRIPTION:Title: Density of rational languages under invariant measures\n
by Herman Goulet-Ouellet as part of One World Combinatorics on Words Semin
ar\n\n\nAbstract\nThe notion of density for languages was studied by Schü
tzenberger in the 60s and by Hansel and Perrin in the 80s. In both cases\,
the authors focused on densities defined by Bernoulli measures. In this t
alk\, I will present new results about densities of regular languages unde
r invariant measures of minimal shift spaces. We introduce a compatibility
condition which implies convergence of the density to a constant which de
pends only on the given rational language. This result can be seen as a fo
rm of equidistribution property. The compatibility condition can be stated
either in terms of return words or of a skew product. The passage between
the two forms is made more transparent using simple combinatorial tools i
nspired by ergodic theory and cohomology. This is joint work with Valérie
Berthé\, Carl-Fredrik Nyberg Brodda\, Dominique Perrin and Karl Petersen
.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/80/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Seda Albayrak
DTSTART:20231121T140000Z
DTEND:20231121T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/81
DESCRIPTION:Title: Quantitative estimates for the size of an intersection of sp
arse automatic sets\nby Seda Albayrak as part of One World Combinatori
cs on Words Seminar\n\n\nAbstract\nIn 1979\, Erdős conjectured that for $
k \\ge 9$\, $2^k$ is\nnot 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 whose ternary expansions omit $2$ has finite inters
ection. A\ntheorem of Cobham (1969) says that if $k$ and $\\ell$ are two\n
multiplicatively independent natural numbers then a subset of the\nnatural
numbers that is both $k$- and $\\ell$-automatic is eventually\nperiodic.
A multidimensional extension of this theorem was later\ngiven by Semenov
(1977). Motivated by Erdős’ conjecture and in\nlight of Cobham’s the
orem\, we give a quantitative version of the\nCobham-Semenov theorem for s
parse automatic sets\, showing that the\nintersection of a sparse $k$-auto
matic subset of $\\mathbb{N}^d$ and a\nsparse $\\ell$-automatic subset of
$\\mathbb{N}^d$ is finite. Moreover\,\nwe give effectively computable uppe
r bounds on the size of the\nintersection in terms of data from the automa
ta that accept these\nsets.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/81/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre Béaur
DTSTART:20231219T140000Z
DTEND:20231219T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/82
DESCRIPTION:Title: All I want for Christmas is an algorithm to detect a Sturmia
n word in an ω-regular language\nby Pierre Béaur as part of One Worl
d Combinatorics on Words Seminar\n\n\nAbstract\nIn the enchanting realm of
CoWLand\, where computer science wizards and mathematics enchanters gathe
r via the magic of the Internet\, a whimsical elf embarks us on a yuletide
adventure. Our quest? To detect Sturmian words hidden in the snowy langua
ges of ω-regular automata. As S-adic representations and discrete lines d
ance around the Christmas tree\, I will present the mischevious magic of d
esubstitution and its algorithmic applications. \n\nI start from weak ω-a
utomata\, that is\, labeled graphs that accept infinite words\, and charac
terize when such automata accept a substitutive word\, a fixed point\, or
a Sturmian word. These methods are effective and provide an algorithm rel
ying on S-adic representations. On the way\, we find some other natural ap
plications in combinatorics on words and discrete geometry. Then\, I will
explain how the methods translate from weak ω-automata to Büchi automata
\, what the limits of our techniques are\, and what are the leads to give
this fairytale a proper conclusion.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/82/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthieu Rosenfeld
DTSTART:20231205T140000Z
DTEND:20231205T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/83
DESCRIPTION:Title: Word reconstruction using queries on subwords or factors
\nby Matthieu Rosenfeld as part of One World Combinatorics on Words Semina
r\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/83/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Clemens Müllner
DTSTART:20240109T140000Z
DTEND:20240109T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/84
DESCRIPTION:Title: Synchronizing automatic sequences along Piatetski-Shapiro se
quences\nby Clemens Müllner as part of One World Combinatorics on Wor
ds Seminar\n\n\nAbstract\nAutomatic sequences - that is\, sequences comput
able by finite automata - have long been studied from the point of view of
combinatorics on words. A notable property of these sequences is that the
ir subword-complexity is at most linear. Avgustinovich\, Fon-Der-Flaass an
d Frid introduced the notion of arithmetic subword-complexity - that is th
e number of different subwords of length $n$ that appear along some arithm
etic progression.\nThey also showed that a special class of synchronizing
automatic sequences have at most linear arithmetic subword-complexity and
some other class of automatic sequences on the alphabet $\\Sigma$ have max
imal possible subword-complexity $|\\Sigma|^n$.\n\nSynchronizing automatic
sequences can be efficiently approximated using periodic functions and ar
e usually more structured than general automatic sequences. We discuss a r
ecent result showing that the arithmetic (and even polynomial) subword-com
plexity of synchronizing automatic sequences grows subexponentially. This
was a key result to show that the subword-complexity of synchronizing auto
matic sequences along regularly growing sequences (such as Piatetski-Shapi
ro sequences) grows subexponentially\, which is in stark contrast to other
automatic sequences such as the Thue-Morse sequence. Moreover\, this was
a key ingredient to obtain rather precise estimates for the arithmetic (an
d polynomial) subword-complexity of general automatic sequences.\n\nThis i
s joint work with Jean-Marc Deshouillers\, Michael Drmota\, Andrei Shubin
and Lukas Spiegelhofer.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/84/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jakub Konieczny
DTSTART:20240123T140000Z
DTEND:20240123T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/85
DESCRIPTION:Title: Arithmetical subword complexity of automatic sequences\n
by Jakub Konieczny as part of One World Combinatorics on Words Seminar\n\n
\nAbstract\nIt is well-known that the subword complexity of an automatic s
equence 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
most $C \\ell$ for a constant $C$ dependent only on $a$. In contrast\, ari
thmetic subword complexity measures the number of subwords which appear al
ong arithmetic progressions\, and can grow exponentially even for very sim
ple automatic sequences. Indeed\, the classical Thue-Morse sequence has ar
ithmetic subword complexity $2^{\\ell}$\, which is the maximal possible co
mplexity for $\\{0\,1\\}$-valued sequence.\n\nTogether with Jakub Byszewsk
i and Clemens Müllner we obtained a decomposition result which allows us
to express any (complex-valued) automatic sequence as the sum of a structu
red part\, which is easy to work with\, and a part which is pseudorandom o
r uniform from the point of view of higher order Fourier analysis. We now
apply these techniques to the study of arithmetic subword complexity of au
tomatic sequences. We show that for each automatic sequence $a$ there exis
ts a parameter $r$ --- which we dub "effective alphabet size" --- such tha
t the arithmetic subword complexity of $a$ is at least $r^{\\ell}$ and at
most $(r+o(1))^{\\ell}$. \n\nThis talk is based on joint work with Jakub B
yszewski and Clemens Müllner\, and is closely related to the previous tal
k of Clemens Müllner at One World Combinatorics on Words Seminar.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/85/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Eric Rowland
DTSTART:20240206T140000Z
DTEND:20240206T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/86
DESCRIPTION:Title: Algebraic power series and their automatic complexity\nb
y Eric Rowland as part of One World Combinatorics on Words Seminar\n\n\nAb
stract\nA theorem of Christol gives a characterization of automatic sequen
ces over a finite field: a sequence is automatic if and only if its genera
ting series is algebraic. Since there are two representations for such a s
equence -- as an automaton and as a bivariate polynomial -- a natural ques
tion is how the size of one representation relates to the size of the othe
r. Bridy used tools from algebraic geometry to bound the size of the minim
al 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 di
agonals of rational functions. Crucially for our interests\, this approach
can be adapted to work not just over a finite field but over the integers
modulo a prime power. This is joint work with Manon Stipulanti and Reem Y
assawi.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/86/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christopher Cabezas
DTSTART:20240220T140000Z
DTEND:20240220T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/87
DESCRIPTION:Title: Large normalizer of odometers and higher-dimensional automat
ic sequences\nby Christopher Cabezas as part of One World Combinatoric
s on Words Seminar\n\n\nAbstract\nFor a $\\mathbb Z^d$ topological dynamic
al system $(X\, T\, \\mathbb Z^d)$\, an isomorphism is a self-homeomorphis
m $\\phi : X\\to X$ such that for some matrix $M \\in GL(d\, \\mathbb Z)$
and any $n \\in \\mathbb Z^d$\, $\\phi \\circ T^n = T^{M_n} \\circ \\phi$\
, where $T^n$ denote the self-homeomorphism of $X$ given by the action of
$n \\in \\mathbb Z^d$. The collection of all the isomorphisms forms a grou
p that is the normalizer of the set of transformations $T^n$. In the one-d
imensional case isomorphisms correspond to the notion of flip conjugacy of
dynamical systems and by this fact are also called reversing symmetries.\
n\nThese isomorphisms are not well understood even for classical systems.
In this talk we will present a description of them for odometers and more
precisely for $\\mathbb Z^2$-constant base odometers\, that is not simple.
We deduce a complete description of the isomorphism of some $\\mathbb Z^2
$ minimal substitution subshifts. Thanks to this\, we will give the first
known example of a minimal zero-entropy subshift with the largest possible
normalizer group.\nThis is a joint work with Samuel Petite (Universitè d
e Picardie Jules Verne).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/87/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Finn Lidbetter
DTSTART:20240305T140000Z
DTEND:20240305T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/88
DESCRIPTION:Title: Improved bound for the Gerver-Ramsey collinearity problem\nby Finn Lidbetter as part of One World Combinatorics on Words Seminar\n
\n\nAbstract\nAbstract: Let $S$ be a finite subset of $\\mathbb{Z}^n$. A v
ector\nsequence $(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\\mathbb{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 the aid of a computer search\, we show how to\nimprove the bou
nd to $189$. We begin by restating the infinite\n$S$-walk as the fixed poi
nt of iterating a morphism defined for a $12$\nletter alphabet.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/88/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Radoslaw Piórkowski
DTSTART:20240416T130000Z
DTEND:20240416T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/89
DESCRIPTION:Title: Universal quantification in automatic structures — an ExpS
pace-hard nut to crack\nby Radoslaw Piórkowski as part of One World C
ombinatorics on Words Seminar\n\n\nAbstract\nAutomatic structures are stru
ctures whose universe and relations can be represented as regular language
s. It follows from the standard closure properties of regular languages th
at the first-order theory of an automatic structure is decidable. \n\nWhil
e existential quantifiers can be eliminated in linear time by application
of a homomorphism\, universal quantifiers are commonly eliminated via the
identity ∀x. Φ ≡ ¬(∃x. ¬Φ). If Φ is represented in the standard
way as an NFA\, a priori this approach results in a doubly exponential bl
ow-up. However\, the recent literature has shown that there are classes of
automatic structures for which universal quantifiers can be eliminated wi
thout this blow-up when treated as first-class citizens and not resorting
to double complementation. The existing lower bounds for some classes of a
utomatic structures show that a singly exponential blow-up is unavoidable
when eliminating a universal quantifier\, but it is not known whether ther
e may be better approaches that avoid the naïve doubly exponential blow-u
p. \nWe answer this question negatively.\n\nIn my talk\, following a short
introduction to the field of automatic structures\, I will present the co
nstruction of a family of NFA representing automatic relations for which t
he minimal NFA recognising the language after a universal projection step
is doubly exponential\, and deciding whether this language is empty is Exp
Space-complete.\n\n\nBased on the paper: https://drops.dagstuhl.de/entitie
s/document/10.4230/LIPIcs.CONCUR.2023.13 \n\nAuthors: Christoph Haase\, R.
P.\n\nKeywords: automatic structures\, universal projection\, tiling probl
ems\, state complexity.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/89/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cor Kraaikamp
DTSTART:20240319T140000Z
DTEND:20240319T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/90
DESCRIPTION:Title: An introduction to $N$ -expansions with a finite set of dig
its\nby Cor Kraaikamp as part of One World Combinatorics on Words Semi
nar\n\n\nAbstract\nIn this talk $N$-expansions\, and in particular $N$-exp
ansions with a finite set\nof digits\, will be introduced. Although $N$-ex
pansions were introduced as\nrecent as 2008 by Ed Burger and some of his s
tudents\, quite a number of\npapers have appeared on these variations of t
he regular continued fraction\nexpansion. By choosing a domain for the und
erlying Gauss-map which does\nnot contain the origin\, a continued fractio
n with finitely many digits was\nintroduced by Niels Langeveld in his MSc-
thesis. It turns out that these\ncontinued fraction algorithms exhibit a v
ery complicated and surprising rich\ndynamical behavior.\n\nThis talk is b
ased on joint work with Yufei Chen (Shanghai\, Delft)\, Jaap\nde Jonge (Uv
A\, Amsterdam)\, Karma Dajani (Utrecht)\, Niels Langeveld\n(Montan U.\, Le
oben)\, Hitoshi Nakada (Keio\, Yokohama)\, and Niels van der\nWekken (Netc
ompany).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/90/
END:VEVENT
BEGIN:VEVENT
SUMMARY:John Campbell
DTSTART:20240402T130000Z
DTEND:20240402T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/91
DESCRIPTION:Title: On the evaluation of infinite products involving automatic s
equences\nby John Campbell as part of One World Combinatorics on Words
Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/91/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michael Baake
DTSTART:20240430T130000Z
DTEND:20240430T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/92
DESCRIPTION:Title: Hats\, CAPs and Spectres\nby Michael Baake as part of On
e World Combinatorics on Words Seminar\n\n\nAbstract\nThe recently discove
red Hat is an aperiodic\nmonotile for the Euclidean plane\, which needs a
reflected\nversion for this property. The Spectre does not have this\n(tin
y) deficiency. We discuss the topological and dynamical\nproperties of the
Hat tiling\, how the CAP relates to it\, and\nwhat the long-range order o
f both tilings is. Finally\, we\nbriefly describe the analogous structure
for the Spectre tiling.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/92/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Josef Rukavicka
DTSTART:20240514T130000Z
DTEND:20240514T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/93
DESCRIPTION:Title: Restivo Salemi property for $\\alpha$-power free languages w
ith $\\alpha \\geq 5$ and $k \\geq 3$ letters\nby Josef Rukavicka as p
art of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn 2009\, S
hur published the following conjecture: Let $L$ be a power-free language a
nd 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-freeness. If $u\,v \\in e
(L)$ then $uwv \\in e(L)$ for some word $w$. Let $L_{k\,\\alpha}$ denote a
n $\\alpha$-power free language over an alphabet with $k$ letters\, where
$\\alpha$ is a positive rational number and $k$ is positive integer. We pr
ove the conjecture for the languages $L_{k\,\\alpha}$\, where $\\alpha\\ge
q 5$ and $k \\geq 3$.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/93/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pascal Ochem
DTSTART:20240528T130000Z
DTEND:20240528T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/94
DESCRIPTION:Title: Characterization of morphic words\nby Pascal Ochem as pa
rt of One World Combinatorics on Words Seminar\n\n\nAbstract\nThe famous H
all-Thue word\, fixed point of the morphism\n0 -> 012\, 1 -> 02\, 2 -> 1\,
is essentially the only infinite\nternary word avoiding squares and the w
ords 010 and 212.\n\nI will present many examples of this phenomenon\, tha
t is\,\nwhen every recurrent word satisfying some avoidance constraints\nh
as the same factor set as a morphic word.\n\nThis is a joint work with Gol
naz Badkobeh\, Matthieu Rosenfeld\,\nL'ubomíra Dvořáková\, Daniela Opo
čenská\, Aseem Baranwal\,\nJames Currie\, Lucas Mol\, Narad Rampersad\,
and Jeffrey Shallit.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/94/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Markus Whiteland
DTSTART:20240611T130000Z
DTEND:20240611T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/95
DESCRIPTION:Title: What I know about Parikh-collinear morphisms\nby Markus
Whiteland as part of One World Combinatorics on Words Seminar\n\n\nAbstrac
t\nA morphism is Parikh-collinear if its adjacency matrix has rank at most
one. For example\, the famous Thue-Morse morphism is such morphism. Some
of their properties have been considered in the literature\, e.g.\, by All
ouche et al. [Comb. Theory 1\, 2021] (in passing) and Cassaigne et al. [In
t. J. Found. Comput. 22\, 2011]\; the latter characterises Parikh-collinea
r morphisms as those morphisms that map any infinite word (over the domain
alphabet) to a word with bounded abelian complexity.\n\nIn this talk I wi
ll focus on properties of Parikh-collinear morphisms and their fixed point
s from the viewpoint of binomial complexities. We will also consider autom
atic (in the sense of Allouche and Shallit) aspects related to such fixed
points.\n\nThe talk is based on joint work with M. Rigo and M. Stipulanti.
\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/95/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julien Cassaigne
DTSTART:20240625T130000Z
DTEND:20240625T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/96
DESCRIPTION:Title: The Heinis spectrum\nby Julien Cassaigne as part of One
World Combinatorics on Words Seminar\n\n\nAbstract\nMany families of infin
ite words (or of subshifts) have a subword complexity\nfunction $p(n)$ tha
t grows linearly. It has sometimes a very simple form\n(such as $n + 1$\,
$2n + 1$\, etc.)\, but often a more complicated behaviour\,\nas for the T
hue-Morse word. In his Ph.D. thesis\, Alex 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\, th
e\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 charac
terize\npoints in $\\Omega$. We present some properties of this set\, and
some\nquestions that we find interesting.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/96/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jamie Simpson
DTSTART:20240709T130000Z
DTEND:20240709T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/97
DESCRIPTION:Title: Palindromic Periodicities\nby Jamie Simpson as part of O
ne World Combinatorics on Words Seminar\n\n\nAbstract\nIf $p$ and $s$ are
palindromes then a factor of the infinite word $(ps)^\\omega$ which has le
ngth at least $|ps|$ is called a palindromic periodicity. In this talk I
will first describe some simple properties of these objects and then show
how they can appear. For example a word which is both periodic and a pali
ndrome 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.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/97/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jia-Yan Yao
DTSTART:20240910T130000Z
DTEND:20240910T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/98
DESCRIPTION:Title: When is an automatic number transparent?\nby Jia-Yan Yao
as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn thi
s talk we introduce a new notion to measure the complexity of automatic nu
mbers\, which are either rational or transcendental. We study basic proper
ties of this notion\, and exhibit an algorithm to compute it. In particula
r\, we shall characterize all the automatic numbers which are transparent.
As applications\, we shall also compute the complexity of some well-known
automatic numbers.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/98/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Elżbieta Krawczyk
DTSTART:20241203T140000Z
DTEND:20241203T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/99
DESCRIPTION:Title: Quasi-fixed points of substitutions and substitutive systems
\nby Elżbieta Krawczyk as part of One World Combinatorics on Words Se
minar\n\n\nAbstract\nWe study automatic sequences and automatic systems (s
ymbolic dynamical systems) generated by general constant length (nonprimit
ive) substitutions. While an automatic system is typically uncountable\, t
he set of automatic sequences is countable\, implying that most sequences
within an automatic system are not themselves automatic. We provide a comp
lete classification of automatic sequences that lie in a given automatic s
ystem in terms of the so-called quasi-fixed points of the substitution def
ining the system. Quasi-fixed points have already appeared implicitly in a
few places (e.g. in the study of substitutivity of lexicographically min
imal points in substitutive systems or in the study of subsystems of subst
itutive systems) and they have been described in detail by Shallit and Wan
g and\, more recently\, B\\'eal\, Perrin\, and Restivo . We conjecture tha
t a similar statement holds for general nonconstant length substitutions.\
n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/99/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yuto Nakashima
DTSTART:20241217T140000Z
DTEND:20241217T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/100
DESCRIPTION:Title: On the Number of Non-equivalent Parameterized Squares in a
String\nby Yuto Nakashima as part of One World Combinatorics on Words
Seminar\n\n\nAbstract\nA string $s$ is called a parameterized square when
$s = xy$ for strings $x$\, $y$ and $x$ and $y$ are parameterized equivalen
t.\nKociumaka et al. showed the number of parameterized squares\, which ar
e non-equivalent in parameterized equivalence\, in a string of length $n$
that contains $\\sigma$ distinct characters is at most $2 \\sigma! n$ [TCS
2016].\nRecently\, we showed that the maximum number of non-equivalent pa
rameterized squares is less than $\\sigma n$\, which significantly improve
s the best-known upper bound by Kociumaka et al.\n\nThis is a joint work w
ith Rikuya Hamai\, Kazushi Taketsugu\, Shunsuke Inenaga\, and Hideo Bannai
(presented at SPIRE 2024).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/100/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luke Schaeffer
DTSTART:20240924T130000Z
DTEND:20240924T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/101
DESCRIPTION:Title: Summation and transduction of automatic sequences\nby L
uke Schaeffer as part of One World Combinatorics on Words Seminar\n\n\nAbs
tract\nWe examine the theory of computing partial sums or transductions in
automatic sequences\, including a theorem of Dekking and its generalizati
on. We give a number of examples involving paperfolding words and Sturmian
sequences.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/101/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mehdi Golafshan
DTSTART:20241008T130000Z
DTEND:20241008T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/102
DESCRIPTION:Title: Factor complexity of the most significant digits and unipot
ent dynamics on a torus\nby Mehdi Golafshan as part of One World Combi
natorics on Words Seminar\n\n\nAbstract\nIn this talk\, we explore the dyn
amics of unipotent flows on a torus and how these techniques lead to inter
esting applications in number theory. Specifically\, I'll focus on the fol
lowing problem: let \\(d\\) be a positive integer\, and \\(a > 0\\) be a r
eal number. Consider a square-free integer \\(b \\geqslant 5\\) such that
\\(a\\) and \\(b\\) are multiplicatively 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 wi
ll present our result\, showing that the complexity function of this seque
nce\, with only a finite number of exceptions\, is a polynomial function.
This work connects dynamics on homogeneous spaces with problems in symboli
c dynamics and number theory\, offering new insights into sequence complex
ity.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/102/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Olivier Carton
DTSTART:20241022T130000Z
DTEND:20241022T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/103
DESCRIPTION:Title: Mahler equations for Zeckendorf numeration\nby Olivier
Carton as part of One World Combinatorics on Words Seminar\n\n\nAbstract\
nLet $U = (u_n)$ be a Pisot numeration system. A sequence $(f_n)$ taking
values\nover a commutative ring $R$\, possibly infinite\, is said to be //
$U$-regular//\nif there exists a //weighted// automaton which outputs $f_n
$ when it reads\n$(n)_U$. For base-$q$ numeration\, with $q ∈ ℕ$\, $q
$-regular sequences\nwere introduced and studied by Allouche and Shallit\,
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 sequen
ces\, and //$q$-Mahler type//\nequations. In particular a $q$-regular sequ
ence gives a solution to an\nequation of $q$-Mahler type\, and conversely\
, the solution of an\n//isolating//\, or Becker\, equation of $q$-Mahler t
ype is $q$-regular.\n\nWe define generalised equations of $Z$-Mahler type\
, based on the Zeckendorf\nnumeration system $Z$. We show that if a sequen
ce over a commutative ring is\n$Z$-regular\, then it is the sequence of co
efficients of a series which is a\nsolution of a $Z$-Mahler equation. Conv
ersely\, if the $Z$-Mahler equation is\nisolating\, then its solutions def
ine $Z$-regular sequences. We provide an\nexample to show that there exis
t non-isolating $Z$-Mahler equations whose\nsolutions do not define $Z$-re
gular sequences. Our proof yields a new\nconstruction of weighted automata
that generate classical $q$-regular\nsequences.\n\nThis is joint work wit
h Reem Yassawi.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/103/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benjamin Hellouin de Menibus
DTSTART:20241105T140000Z
DTEND:20241105T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/104
DESCRIPTION:Title: String attractors for infinite words\nby Benjamin Hello
uin de Menibus as part of One World Combinatorics on Words Seminar\n\n\nAb
stract\nA string attractor of a word w is a set of marked positions such t
hat every factor of w has an occurrence that crosses one of the marked pos
itions. This is a recent concept whose motivation comes from the study of
compression algorithms\, but that was studied very soon after for its comb
inatorial properties. In particular\, the size or span of the smallest str
ing attractor for a word can be seen as a measure of its complexity\, and
this point of view led to studying smallest string attractors for families
of classical words\, such as the prefixes of the Fibonacci word.\n\nWhile
it is fruitful to study smallest string attractors on finite prefixes or
factors of infinite words\, we can also define string attractors directly
on infinite words. Unfortunately\, there is no good notion of smallest str
ing attractor in this setting\, except when there is a finite one\, which
in the one-sided case means that the word is periodic.\n\nFortunately\, th
e two-sided case is more rich in this regard\, and is the topic of this ta
lk. We study and completely characterise two-sided infinite words that adm
it a finite string attractor\, and relate the size of the smallest attract
or to their complexity function. We also get another characterisation of (
quasi-)Sturmian words. I will also mention some side results regarding per
iodic string attractors and / or string attractors for shifts.\n\nThis is
a joint work with Pierre Béaur and France Gheeraert.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/104/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Léo Vivion
DTSTART:20241119T140000Z
DTEND:20241119T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/105
DESCRIPTION:Title: Balancedness constants of words generated by billiards in t
he hypercube\nby Léo Vivion as part of One World Combinatorics on Wor
ds Seminar\n\n\nAbstract\nA hypercubic billiard word in dimension $d$ is a
n 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 fac
es are labeled by the same letter. Square billiard words generated by a (b
illiard ball with an initial) momentum with rationally independent coordin
ates are Sturmian\, so hypercubic billiard words generated by a momentum w
ith rationally independent coordinates are one dynamical generalization of
Sturmian words. Hence\, it is natural to ask which properties satisfied b
y Sturmian words are still satisfied by hypercubic billiard words.\n\nWhil
e the subword complexity of hypercubic billiard words has been extensively
studied at the end of the 1990s and the beginning of the 2000s (Arnoux\,
Mauduit\, Shiokawa and Tamura 1994\, Baryshnikov 1995 and Bédaride 2003-2
009)\, their abelian properties have been much less studied: only Vuillon
(2003) initiated the study of their balancedness.\n\nIn this talk\, I will
first recall the results obtained by Vuillon\, and then\, give a complete
characterization of the imbalance of hypercubic billiard words generated
by a momentum with rationally independent coordinates. In a second part\,
I will also discuss the case of momenta with rationally dependent coordina
tes.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/105/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christophe Reutenauer
DTSTART:20250114T140000Z
DTEND:20250114T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/106
DESCRIPTION:Title: Christoffel matrices and Sturmian determinants\nby Chri
stophe Reutenauer as part of One World Combinatorics on Words Seminar\n\n\
nAbstract\nWork 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 b
y 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 determ
inants\; ordering them suitably\, these $n+1$ determinants form a word on
a two- or three-letter alphabet contained in $Z$\; this word is perfectly
clustering. If there are three letters\, then one of them is the sum of th
e two others.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/106/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lucas Mol
DTSTART:20250128T140000Z
DTEND:20250128T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/107
DESCRIPTION:Title: Avoiding abelian and additive powers in rich words\nby
Lucas Mol as part of One World Combinatorics on Words Seminar\n\n\nAbstrac
t\nWe 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 length and su
m of the images of the letters are linear functions of the letters. This
allows us to prove the additive power-freeness of our constructions using
a recent variation of the template method due to Currie\, Mol\, Rampersad\
, and Shallit.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/107/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Josef Rukavicka
DTSTART:20250211T140000Z
DTEND:20250211T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/108
DESCRIPTION:Title: Palindromic length of infinite aperiodic words\nby Jose
f Rukavicka as part of One World Combinatorics on Words Seminar\n\n\nAbstr
act\nThe palindromic length of the finite word $v$ is equal to the minimal
number of palindromes whose concatenation is equal to $v$. It was conject
ured in 2013 that for every infinite aperiodic word $x$\, the palindromic
length of its factors is not bounded.\nWe prove this conjecture to be true
.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/108/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bartek Pawlik
DTSTART:20250225T140000Z
DTEND:20250225T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/109
DESCRIPTION:Title: Words Avoiding Tangrams\nby Bartek Pawlik as part of On
e World Combinatorics on Words Seminar\n\n\nAbstract\nWork in collaboratio
n with Michał Dębski\, Jarosław Grytczuk\, Jakub Przybyło and Małgorz
ata Śleszyńska-Nowak.\n\nIf\, in a given word $W$\, each letter appears
an even number of times\, then $W$ can be split into two identical\, disjo
int subwords. For example\, the word $\\mathtt{hotshots}$ can be split int
o two $\\mathtt{hots}$ by dividing the word exactly in the middle: $\\math
tt{hots\\\,|\\\,hots}$. More generally\, any square can be separated into
two identical words with a single cut. The word $\\mathtt{tattletale}$ req
uires three cuts: $\\mathtt{tat\\\,|\\\,tle\\\,|\\\,ta\\\,|\\\,le}$ to spl
it it into two words $\\mathtt{tatle}$. The minimal number of cuts needed
to divide a word $W$ into two identical subwords is called the {\\it cut n
umber} of $W$. During the lecture\, I will discuss several topics related
to the cut number.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/109/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre Letouzey
DTSTART:20250311T140000Z
DTEND:20250311T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/110
DESCRIPTION:Title: Generalizing some Hofstadter functions: G\, H and beyond\nby Pierre Letouzey as part of One World Combinatorics on Words Seminar\
n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/110/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vuong Bui
DTSTART:20250325T140000Z
DTEND:20250325T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/111
DESCRIPTION:Title: An explicit condition for boundedly supermultiplicative sub
shifts\nby Vuong Bui as part of One World Combinatorics on Words Semin
ar\n\n\nAbstract\nWe study some properties of the growth rate of $L(A\,F)
$\, that is\, the language of words over the alphabet $A$ avoiding the set
of forbidden 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 $\\alp
ha^n$ and $C\\alpha^n$. In some settings\, our condition provides a way to
compute $C$\, which implies that $\\alpha$\, the growth rate of the langu
age\, is also computable whenever our condition holds.\nWe also apply our
technique to the specific setting of power-free words where the argument c
an be slightly refined to provide better bounds. Finally\, we apply a simi
lar idea to $F$-free circular words and in particular we make progress tow
ard a conjecture of Shur about the number of square-free circular words.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/111/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hajime Kaneko
DTSTART:20250408T130000Z
DTEND:20250408T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/112
DESCRIPTION:Title: Analogs of Markoff and Lagrange spectra on one-sided shift
spaces\nby Hajime Kaneko as part of One World Combinatorics on Words S
eminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/112/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Be'eri Greenfeld
DTSTART:20250422T130000Z
DTEND:20250422T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/113
DESCRIPTION:Title: On the Complexity of Infinite Words\nby Be'eri Greenfel
d as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nGiven
an infinite word $w$\, its complexity function $p_w(n)$ counts the number
of distinct subwords of length $n$ it contains. A longstanding open probl
em in the combinatorics of infinite words is the {\\it inverse problem}: d
escribe which functions $f: \\mathbb N \\to \\mathbb N$ arise as complexit
y functions of infinite words. Such functions must be non-decreasing and\,
unless eventually constant\, strictly increasing\; they must also be subm
ultiplicative\, i.e.\, $f(n+m)≤f(n)f(m)$. Many interesting results\, bot
h positive and negative\, have been obtained in this direction.\n\nWe reso
lve this problem up to asymptotic equivalence in the sense of large-scale
geometry. Specifically\, given any increasing\, submultiplicative function
$f$\, we construct an infinite recurrent word $w$ such that $c f(cn) ≤
p_w(n) ≤ d f(dn)$ for some constants $c\,d>0$. For uniformly recurrent w
ords\, we obtain a weaker version allowing a linear error factor. Time per
mitting\, we will discuss connections and applications of these results to
asymptotic questions in algebra.\n\nJoint work with C. G. Moreira and E.
Zelmanov.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/113/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jarkko Peltomäki
DTSTART:20250506T130000Z
DTEND:20250506T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/114
DESCRIPTION:Title: The repetition threshold for ternary rich words\nby Jar
kko Peltomäki as part of One World Combinatorics on Words Seminar\n\n\nAb
stract\nIn the recent years\, it has been popular to determine the least c
ritical exponent in specific families of infinite words. In this talk\, I
will explain what is known about the least critical exponents for infinite
words that are rich in palindromes. In particular\, I will outline the pr
oof of our result that the least critical exponent for ternary rich infini
te words equals $1 + 1/(3 - \\mu) \\approx 2.25876324$\, where $\\mu$ is t
he unique real root of the polynomial $x^3 - 2x^2 - 1$. This result is bas
ed on proving a structure theorem for ternary rich infinite words that avo
id $16/7$-powers. In addition\, I discuss some recent progress on determin
ing the least asymptotic critical exponents for rich infinite words.\n\nJo
int work with L. Mol and J. D. Currie.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/114/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pranjal Jain
DTSTART:20250520T130000Z
DTEND:20250520T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/115
DESCRIPTION:Title: Partial Sums of Binary Subword-Counting Sequences\nby P
ranjal Jain as part of One World Combinatorics on Words Seminar\n\n\nAbstr
act\nLet $w$ be a finite word over the alphabet $\\{0\,1\\}$. For any natu
ral number $n$\, let $s_w(n)$ denote the number of occurrences of $w$ in t
he binary expansion of $n$ as a scattered subsequence. The talk aims to pr
ovide 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 techniques
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 the idea
s using the case of $w=01\,011$. The talk is based on joint work with Shuo
Li.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/115/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Curtis Bright
DTSTART:20250603T130000Z
DTEND:20250603T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/116
DESCRIPTION:Title: Mathematical Problems with SATisfying Solutions\nby Cur
tis Bright as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nAutomated reasoning tools have been effectively used to solve a variet
y of problems in discrete mathematics. In this talk\, I will introduce sa
tisfiability (SAT) solvers and highlight a variety of problems in discrete
mathematics that have been tackled with a SAT solver. As a case study\,
I will demonstrate how a SAT solver can be used to make progress on a ques
tion arising in combinatorics on words involving North-East lattice paths.
\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/116/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noy Soffer Aranov
DTSTART:20250617T130000Z
DTEND:20250617T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/117
DESCRIPTION:Title: Escape of Mass of Sequences\nby Noy Soffer Aranov as pa
rt of One World Combinatorics on Words Seminar\n\n\nAbstract\nOne way to s
tudy the distribution of nested quadratic number fields satisfying fixed a
rithmetic relationships is through the evolution of continued fraction exp
ansions. In the function field setting\, it was shown by de Mathan and Teu
llie that given a quadratic irrational $\\Theta$\, the degrees of the peri
odic part of the continued fraction of $t^n\\Theta$ are unbounded. Paulin
and Shapira improved this by proving that quadratic irrationals exhibit pa
rtial escape of mass. Moreover\, they conjectured that they must exhibit f
ull escape of mass. We construct counterexamples to their conjecture in ev
ery characteristic. In this talk we shall discuss the technique of proof a
s well as the connection between escape of mass in continued fractions\, H
ecke trees\, and number walls. This is part of joint works with Erez Nesha
rim and Uri Shapira and with Steven Robertson.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/117/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Elżbieta Krawczyk
DTSTART:20250715T130000Z
DTEND:20250715T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/118
DESCRIPTION:Title: Quasi-fixed points of substitutions and substitutive system
s\nby Elżbieta Krawczyk as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nWe study automatic sequences and automatic systems (
symbolic dynamical systems) generated by general constant length (nonprimi
tive) substitutions. 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 com
plete classification of automatic sequences that lie in a given automatic
system in terms of the so-called quasi-fixed points of the substitution de
fining the system. Quasi-fixed points have already appeared implicitly in
a few places (e.g. in the study of substitutivity of lexicographically min
imal points in substitutive systems or in the study of subsystems of subst
itutive systems) and they have been described in detail by Shallit and Wan
g and\, more recently\, Béal\, Perrin\, and Restivo . We conjecture that
a similar statement holds for general nonconstant length substitutions.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/118/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gandhar Joshi
DTSTART:20250902T130000Z
DTEND:20250902T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/119
DESCRIPTION:Title: Monochromatic Arithmetic Progressions in Sturmian sequences
\nby Gandhar Joshi as part of One World Combinatorics on Words Seminar
\n\n\nAbstract\nThis is joint work with Dan Rust. We define Monochromatic
arithmetic progression (MAP) as the repetition of a symbol (traditionally
colour) with a constant difference in a sequence. We study thresholds of t
he lengths of MAPs in the Fibonacci word in our paper https://doi.org/10.1
016/j.tcs.2025.115391\, which not only resolves a few problems left open b
y previous works revolving around MAPs in symbolic sequences but also reve
als a straightforward method to find a formula that finds longest lengths
of MAPs for all Sturmians. This extension is dealt with in the author's Ph
D thesis.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/119/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kaisei Kishi
DTSTART:20250916T130000Z
DTEND:20250916T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/120
DESCRIPTION:Title: Net Occurrences in Fibonacci and Thue-Morse Words\nby K
aisei Kishi as part of One World Combinatorics on Words Seminar\n\n\nAbstr
act\nIn a string $T$\, an occurrence of a substring $S=T[i ... j]$ is a ne
t 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$. The numb
er of net occurrences of $S$ in $T$ is called its net frequency. Compared
with ordinary frequency\, net frequency highlights the more significant oc
currences of $S$ in $T$. In this talk\, I will present several properties
of net occurrences and describe techniques to identify all the net occurre
nces in Fibonacci and Thue-Morse words. In particular\, I will explain the
technique to characterize the occurrences of smaller-order Fibonacci and
Thue-Morse words. This is a joint work with Peaker Guo.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/120/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Idrissa Kaboré
DTSTART:20251028T140000Z
DTEND:20251028T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/121
DESCRIPTION:Title: POSTPONED\nby Idrissa Kaboré as part of One World Comb
inatorics on Words Seminar\n\n\nAbstract\nIn this talk\, first\, I will re
call the notions of modulo-recurrent words and of window complexity. These
notions are introduced in 2007. Then\, I present some properties of these
notions. After that\, I will present the notions of uniform modulo-recurr
ence and of strong modulo-recurrence. These notions are defined recently i
n a joint work with Julien Cassaigne. Sturmian words are uniformly (resp.
strongly) modulo-recurrent words. Then\, I will address the window complex
ity of the Thue-Morse. To finish\, I will present a recurrent aperiodic wo
rd with bounded window complexity.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/121/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aleksi Vanhatalo
DTSTART:20251111T140000Z
DTEND:20251111T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/122
DESCRIPTION:Title: Exponents of words under injective morphisms\nby Aleksi
Vanhatalo as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nA very common problem type in combinatorics on words is to construct w
ords (under constraints) that avoid repetition. This is often done by cons
tructing suitable morphisms. Here we flip the setup: we ask how good morph
isms are at introducing repetitions into words. Periodic morphisms are tri
vially very good at this\, but how about less trivial classes of morphisms
?\n\nWe consider a few variations of this question. We characterize finite
words that do not have an upper bound on fractional or integer exponents
when mapped via injective morphisms. Then we consider the asymptotic criti
cal exponent of infinite words. While we consider all finite alphabet size
s\, these variations are better understood in the binary case. This talk i
s an extended version of the one presented at DLT 2025. It is based on joi
nt work with Eva Foster and Aleksi Saarela\, and on ongoing research.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/122/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ignacio Mollo
DTSTART:20251125T140000Z
DTEND:20251125T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/123
DESCRIPTION:Title: Is fully shuffling a rational operation?\nby Ignacio Mo
llo as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA s
huffler is a 3-tape transducer specialized in the shuffling of words. Thes
e automata define rational sets in the so-called shuffling monoid\, which
map directly to regular shuffle languages. In this talk we look at rationa
l relations of words and wonder whether their full shuffle is rational: we
conclude that it's very rare that the full shuffle of a rational relation
remains rational but find very interesting examples where rationality can
be assured.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/123/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Antoine Julien
DTSTART:20251014T130000Z
DTEND:20251014T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/124
DESCRIPTION:Title: On balance properties of hypercubic billiard words\nby
Antoine Julien as part of One World Combinatorics on Words Seminar\n\n\nAb
stract\nThis presentation is concerned with hypercubic billiards with irra
tional trajectories. In this talk\, I will present the relationship betwee
n balance properties in hypercubic billiards\, and subshift cohomology. \n
\nMore precisely\, I will define cohomology for subshifts and (time permit
ting) illustrate with examples of how cohomology has previously been used
in symbolic dynamics. Then\, I will present the link between cohomology an
d balance for billiard sequences. Finally\, I will explain how results of
Kellendonk and Sadun on the dimension of some cohomology spaces implies th
at billiard words in cubes of dimension at least 3 cannot be balanced on a
ll factors.\n\nIn the case of billiards in the cube\, we also showed (usin
g other methods) that these sequences are not balanced on factors of lengt
h 2.\n\nJoint work with Nicolas Bédaride and Valérie Berthé.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/124/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Florin Manea
DTSTART:20251209T140000Z
DTEND:20251209T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/125
DESCRIPTION:Title: Linear Time Subsequence and Supersequence Regex Matching\nby Florin Manea as part of One World Combinatorics on Words Seminar\n\n
\nAbstract\nIt is well-known that checking whether a given string $w$ matc
hes 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 ti
me of $O((|w|⋅ |r|)^{1-\\varepsilon})$ assuming the strong exponential t
ime hypothesis (SETH). We study a different matching paradigm where we ask
instead whether $w$ has a subsequence that matches $r$\, and show that re
gex matching in this sense can be solved in linear time $O(|w| + |r|)$. Fu
rther\, the same holds if we ask for a supersequence. We show that the qua
ntitative variants where we want to compute a longest or shortest subseque
nce 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
instead of the subsequence and supersequence relation. We further study th
e complexity of the universal problem where we ask if all subsequences (or
supersequences\, infixes\, prefixes\, left-extensions or extensions) of a
n 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\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/125/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Louis Marin
DTSTART:20260106T140000Z
DTEND:20260106T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/127
DESCRIPTION:Title: Maximal 2-dimensional binary words of bounded degree\nb
y Louis Marin as part of One World Combinatorics on Words Seminar\n\n\nAbs
tract\n(Authors: Alexandre Blondin Massé\, Alain Goupil\, Raphael L'Heure
ux\, Louis Marin)\n\nLet $d$ be an integer between $0$ and $4$\, and $W$ b
e a $2$-dimensional word of dimensions $h \\times w$ on the binary alphabe
t $\\{0\, 1\\}$\, where $h\, w \\in \\mathbb Z > 0$. Assume that each occu
rrence 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 o
ccur 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$ r
ectangle.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/127/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Savinien Kreczman
DTSTART:20260120T140000Z
DTEND:20260120T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/128
DESCRIPTION:Title: Factor complexity and critical exponent of words in a Thue-
Morse family\nby Savinien Kreczman as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nThe Thue-Morse\, Fibonacci-Thue-Morse and
Allouche-Johnson words are related to the binary\, Zeckendorf and Narayana
numeration systems respectively\, as they count the parity of the number
of ones in representations of natural numbers in those systems. These thre
e numeration systems can be seen as the special cases for k=1\,2\,3 of a p
ositional numeration 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 element
s in a family of binary words related to those numeration systems.\n\nIn a
recent preprint\, J.Shallit put forth two conjectures on words of this fa
mily\, the first concerning the first difference of their factor complexit
y and the second concerning their asymptotic critical exponent. In this ta
lk\, we will prove both conjectures by studying bispecial factors within t
hose words. We will highlight a method by K.Klouda allowing us to fully li
st those bispecial factors and show how this list allows us to attack the
conjectures in question.\nJoint work with L'ubomíra Dvořáková and Edit
a Pelantová.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/128/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Annika Huch
DTSTART:20260203T140000Z
DTEND:20260203T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/129
DESCRIPTION:Title: A Word Reconstruction Problem for Polynomial Regular Langua
ges\nby Annika Huch as part of One World Combinatorics on Words Semina
r\n\n\nAbstract\nThe reconstruction problem concerns the ability to unique
ly determine an unknown word from querying information on the number of oc
currences of chosen subwords. In the joined work with M. Golafshan and M.
Rigo we focused on the reconstruction problem when the unknown word belong
s to a known polynomial regular language\, i.e.\, \nits growth function is
bounded by a polynomial. Exploiting the combinatorial and structural prop
erties of these languages\, we are able to translate queries into polynomi
al equations and transfer the problem of unique reconstruction to finding
those sets of queries such that their polynomial equations have a unique i
nteger solution.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/129/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Steven Robertson
DTSTART:20260217T140000Z
DTEND:20260217T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/130
DESCRIPTION:Title: Number walls of automatic sequences\nby Steven Robertso
n as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nGiven
any one-dimensional sequence S\, one can generate a unique two-dimensiona
l sequence by considering the determinants of the Toeplitz matrices define
d by S. This is known as the number wall of S. It is conjectured that if S
is automatic\, then the number wall of S is itself a two-dimensional auto
matic sequence. In this talk\, we will discuss evidence towards this conje
cture as well as some recent partial results. The talk aims to be accessib
le for people with no experience of number walls.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/130/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ingrid Vukusic
DTSTART:20260303T140000Z
DTEND:20260303T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/131
DESCRIPTION:Title: Balanced rectangles over Sturmian words\nby Ingrid Vuku
sic as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nOne
of the many properties of the famous infinite Fibonacci word $01001010\\c
dots$ is that it is \\textit{balanced}. This means that any two blocks of
the same length have either the same weight or their weights are off by $1
$. Results by Berth\\'e and Tijdeman show that a 2-dimensional variant of
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 completel
y general Sturmian words. The proof is based on Diophantine approximation\
, and I will explain why Ostrowski representations are ``everything one co
uld wish for''.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/131/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwenaël Richomme
DTSTART:20260317T140000Z
DTEND:20260317T150000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/132
DESCRIPTION:Title: On some 2-binomial coefficients of binary words: geometrica
l interpretation\, partitions of integers\, and fair words\nby Gwenaë
l Richomme as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nThe binomial notation $\\binom{w}{u}$ represents the number of occurre
nces of the word\n$u$ as a (scattered) subword in $w$. We first introduce
and study possible uses of\na geometrical interpretation of $\\binom{w}{ab
}$ and \\binom{w}{ba} when $a$ and $b$ are distinct\nletters. We then stud
y the structure of the $2$-binomial equivalence class of a\nbinary word $w
$ (two words are $2$-binomially equivalent if they have the same\nbinomial
coefficients\, that is\, the same numbers of occurrences\, for each word\
nof length at most $2$). Especially we explain the existence of an isomorp
hism\nbetween the graph of the $2$-binomial equivalence class of $w$ with
respect to a\nparticular rewriting rule and the lattice of partitions of t
he integer \\binom{w}{ab}\nwith \\binom{w}{a} parts and greatest part boun
ded by \\binom{w}{b}. Finally we study binary\nfair words\, the words over
$\\{a\, b\\}$ having the same numbers of occurrences of $ab$\nand $ba$ as
subwords $(\\binom{w}{ab} = \\binom{w}{ba})$. In particular\, we sketch a
proof of a recent\nconjecture related to a special case of the least squa
re approximation.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/132/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Paulina Cecchi Bernales
DTSTART:20260331T130000Z
DTEND:20260331T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/133
DESCRIPTION:Title: Interplay between combinatorics and dynamical properties in
minimal symbolic systems\nby Paulina Cecchi Bernales as part of One W
orld Combinatorics on Words Seminar\n\n\nAbstract\nSymbolic systems\, also
known as subshifts\, are topological dynamical systems whose phase space
consists of infinite sequences of symbols\, evolving under the action of t
he (left) shift transformation. As infinite words\, the elements of a symb
olic system possess combinatorial properties associated with their languag
e\, and it is natural to ask how these combinatorial properties determine
or interact with the properties of the system as a dynamical system\, or v
ice versa. In this talk\, I will briefly review the basic notions of symbo
lic systems and some classical results which connect their combinatorial a
nd dynamical properties\, particularly for subshifts generated by substitu
tions. I will then present more recent results illustrating the impact of
combinatorics on the spectral properties of minimal subshifts. In these re
sults\, combinatorial objects such as extension graphs or coboundaries wil
l play an important role. This is a part of a joint work with V. Berthé a
nd B. Espinoza.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/133/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Idrissa Kaboré
DTSTART:20260414T130000Z
DTEND:20260414T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/134
DESCRIPTION:Title: On modulo-recurrence and window complexity in infinite word
s\nby Idrissa Kaboré as part of One World Combinatorics on Words Semi
nar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/134/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bastiàn Espinoza
DTSTART:20260428T130000Z
DTEND:20260428T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/135
DESCRIPTION:Title: The Thue-Morse word in base 3/2\nby Bastiàn Espinoza a
s part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA rich f
amily of symbolic dynamical systems of low complexity is given by automati
c sequences. These sequences are obtained by feeding the base-$k$ expansio
ns of integers\, for a fixed integer base $k$\, into a finite automaton.\n
In this talk\, we turn to automatic sequences in rational bases\, using as
a guiding example a rational-base analogue of one of the most classical i
nteger-base automatic words.\nNamely\, we consider the Thue--Morse word in
base $3/2$\, whose $n$-th term is given by the sum modulo 2 of the digits
in the base-$3/2$ representation of $n$.\nOur results show that\, althoug
h this base-$3/2$ variant is substantially more complex than classical aut
omatic words (for instance\, it is not generated by iterating a single sub
stitution\, and its factor complexity grows superlinearly) it nevertheless
retains several characteristic properties of the integer-automatic world.
\nMore precisely\, we prove uniform recurrence\, establish the existence o
f letter frequencies\, and show several combinatorial symmetries of its la
nguage analogous to those of the classical base-2 word.\nOur approach reli
es on describing the word via the periodic iteration of two substitutions\
, studying the induced action of these substitutions on the $2$-adic integ
ers\, and applying Pontryagin duality on this group.\nThis is joint work w
ith Julien Cassaigne\, Michel Rigo\, and Manon Stipulanti.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/135/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Léo Vivion
DTSTART:20260512T130000Z
DTEND:20260512T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/136
DESCRIPTION:by Léo Vivion as part of One World Combinatorics on Words Sem
inar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/136/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Reem Yassawi
DTSTART:20260526T130000Z
DTEND:20260526T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/137
DESCRIPTION:by Reem Yassawi as part of One World Combinatorics on Words Se
minar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/137/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ľubomíra Dvořáková
DTSTART:20260609T130000Z
DTEND:20260609T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/138
DESCRIPTION:Title: Attractors of sequences coding beta-integers\nby Ľubom
íra Dvořáková as part of One World Combinatorics on Words Seminar\n\n\
nAbstract\nString attractor is an intensively studied object in Combinator
ics on Words.\nIn our talk\, we will recall known results and also some pr
eviously used techniques.\nWe will then describe minimal string attractors
of prefixes of simple Parry sequences.\nThese sequences form a coding of
distances between consecutive beta-integers in numeration systems with a r
eal base beta.\nSimple Parry sequences have been recently studied from thi
s point of view and (not necessarily minimal) attractors of their prefixes
have been described and a conjecture that attractors of alphabet size sho
uld be sufficient was stated. We prove this conjecture. Moreover\, we prov
ide attractors of prefixes of some particular form of binary non-simple Pa
rry sequences.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/138/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Delaram Moradi
DTSTART:20260707T130000Z
DTEND:20260707T140000Z
DTSTAMP:20260422T225703Z
UID:CombinatoricsOnWords/139
DESCRIPTION:by Delaram Moradi as part of One World Combinatorics on Words
Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/139/
END:VEVENT
END:VCALENDAR