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:20260404T110833Z
UID:CombinatoricsOnWords/1
DESCRIPTION:Title: Extremal Square-Free Words and Variations\nby Luca
s Mol (University of Winnipeg) as part of One World Combinatorics on Words
Seminar\n\n\nAbstract\nA square-free word $w$ over a fixed alphabet $\\Si
gma$ is extremal if every word obtained from $w$ by inserting a single let
ter from $\\Sigma$ (at any position) contains a square. Grytczuk et al. re
cently introduced the concept of extremal square-free word\, and demonstra
ted that there are arbitrarily long extremal square-free words over a tern
ary alphabet. One can define extremal overlap-free words\, and more genera
lly\, extremal $\\beta$-free words\, analogously. We characterize the leng
ths of extremal square-free ternary words\, and the lengths of extremal ov
erlap-free binary words. We also establish that there are arbitrarily long
extremal $\\beta$-free binary words for every $2 < \\beta \\leq 8/3$. We
include a variety of interesting conjectures and open questions.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Rigo (University of Liège)
DTSTART:20200713T130000Z
DTEND:20200713T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/2
DESCRIPTION:Title: Binomial^3 : coefficients\, equivalence\, complexity
…\nby Michel Rigo (University of Liège) as part of One World Combin
atorics on Words Seminar\n\n\nAbstract\nThe binomial coefficient $x \\choo
se y$ of the words $x$ and $y$ is the number of times $y$ appears as a (sc
attered) subword of $x$. This concept has received a lot of attention\, e.
g.\, Simon's congruence\, Parikh matrices\, reconstruction problem\, ... A
few years ago\, we introduced the $k$-binomial equivalence: Two words $u$
and $v$ are $k$-binomially equivalent if the binomial coefficients $u \\c
hoose x$ and $v \\choose x$ agree for all words $x$ of length up to $k$. T
his is a refinement of the usual abelian equivalence.\n\nFirst\, I will re
view several results (joint work with P. Salimov\, M. Lejeune\, J. Leroy\,
M. Rosenfeld) related to $k$-binomial complexity (where factors of length
$n$ are counted up to $k$-binomial equivalence) for Sturmian words\, Thue
-Morse word and Tribonacci word. Then I will concentrate on $k$-binomial e
quivalence classes for finite words. In particular\, I will discuss the fa
ct that the submonoid generated by the generators of the free nil-$2$ grou
p on $m$ generators is isomorphic to the quotient of the free monoid $\\{1
\,...\,m\\}^∗$ by the $2$-binomial equivalence (joint work with M. Lejeu
ne\, M. Rosenfeld).\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laurent Vuillon (University of Savoie)
DTSTART:20200720T130000Z
DTEND:20200720T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/3
DESCRIPTION:Title: Combinatorics on words for Markoff numbers\nby Lau
rent Vuillon (University of Savoie) as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nMarkoff numbers are fascinating integers rela
ted to number\ntheory\, Diophantine equation\, hyperbolic geometry\, conti
nued fractions\nand Christoffel words. Many great mathematicians have work
ed on these\nnumbers and the $100$ years famous uniqueness conjecture by F
robenius is\nstill unsolved. In this talk\, we state a new formula to comp
ute the\nMarkoff numbers using iterated palindromic closure and the Thue-M
orse\nsubstitution. The main theorem shows that for each Markoff number $m
$\,\nthere exists a word $v\\in \\{a\,b\\}^*$ such that $m−2$ is equal t
o the length of the iterated palindromic\nclosure of the iterated antipali
ndromic closure of the word $av$. This\nconstruction gives a new recursive
construction of the Markoff numbers\nby the lengths of the words involved
in the palindromic closure.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:James Currie (University of Winnipeg)
DTSTART:20200727T130000Z
DTEND:20200727T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/4
DESCRIPTION:Title: Remarks on Pansiot encodings\nby James Currie (Uni
versity of Winnipeg) as part of One World Combinatorics on Words Seminar\n
\n\nAbstract\nPansiot encodings were an essential ingredient in the soluti
on of Dejean's conjecture. We discuss these encodings\, and the related gr
oup theoretic notions\, in a way perhaps more natural to combinatorics on
words\, namely\, in terms of De Bruijn graphs. We discuss variations on Pa
nsiot encodings\, with applications to circular words\, and to the undirec
ted threshold problem.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Reem Yassawi (The Open University)
DTSTART:20200914T130000Z
DTEND:20200914T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/5
DESCRIPTION:Title: The Ellis semigroup of bijective substitution shifts\nby Reem Yassawi (The Open University) as part of One World Combinatori
cs on Words Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jarkko Peltomäki (University of Turku)
DTSTART:20200928T130000Z
DTEND:20200928T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/6
DESCRIPTION:Title: Avoiding abelian powers cyclically\nby Jarkko Pelt
omäki (University of Turku) as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nA finite word $w$ avoids abelian $N$-powers cyclical
ly if for each\nabelian $N$-power of period $m$\, we have $m \\geq |w|$. T
his notion\ngeneralizes circular avoidance of $N$-powers in two ways. Firs
tly\n"power" is replaced by "abelian power" and secondly circular avoidanc
e\nconcerns only the conjugacy class of a word\, but here we require even\
nmore. Let $\\mathcal{A}(k)$ be the least integer $N$ such that for all\n$
n$ there exists a word of length $n$ over a $k$-letter alphabet that\navoi
ds abelian $N$-powers cyclically. Let $\\mathcal{A}_\\infty(k)$ be the\nle
ast integer $N$ such that there exist arbitrarily long words over a\n$k$-l
etter alphabet that avoid abelian $N$-powers cyclically.\n\nI will sketch
the proofs of the following results: 1) $5 \\leq\n\\mathcal{A}(2) \\leq 8$
\, $3 \\leq \\mathcal{A}(3) \\leq 4$\, $2 \\leq\n\\mathcal{A}(4) \\leq 3$\
, $\\mathcal{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 permits\, I will discuss an\napplication to the growth rates of expo
nents of abelian powers occurring\nin infinite binary words.\n\nSorry\, no
video available\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jarosław Grytczuk (The Jagiellonian University)
DTSTART:20201005T130000Z
DTEND:20201005T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/7
DESCRIPTION:Title: Graph Coloring and Combinatorics on Words\nby Jaro
sław Grytczuk (The Jagiellonian University) as part of One World Combinat
orics on Words Seminar\n\n\nAbstract\nI will present a few problems inspir
ed mutually by various issues studied in the two disciplines of the title.
For instance\, given any sequence of 3-letter alphabets\, is it possible
to pick a letter from each alphabet so that the resulting word is {\\it sq
uare-free}? 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 m
ore different letters in the play\, the easier to avoid repeated factors).
While more than one has attacked the problem\, the question remains unans
wered\, which is especially frustrating as it has a positive answer with 4
-letter alphabets.\n\nThe above question was originally motivated by the {
\\it list coloring} problem\, a very popular topic in graph coloring. Howe
ver\, the opposite direction of inspiration also leads to intriguing matte
rs. For example\, how many letters are needed to label the vertices of a {
\\it planar graph} so that any word occurring along a simple path is squar
e-free? It has been recently proved that 768 letters suffice\, but for a l
ong time 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://stable.researchseminars.org/talk/CombinatoricsOnWords/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Dekking (Technische Universiteit Delft)
DTSTART:20201019T130000Z
DTEND:20201019T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/8
DESCRIPTION:Title: The structure of Zeckendorf representations and base $
\\varphi$ expansions\nby Michel Dekking (Technische Universiteit Delft
) as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn th
e Zeckendorf numeration system natural numbers are represented as sums of
Fibonacci numbers. In base $\\varphi$ natural numbers are represented as s
ums of powers of the golden mean $\\varphi$. Both representations have dig
its 0 and 1\, where the word 11 is not allowed. We know that the Fibonacci
numbers\, and the powers of $\\varphi$ are closely related\, as\, for exa
mple\, in the relation $\\varphi^n=F_{n-1}+F_n\\varphi$. In fact\, Frougny
and Sakarovitch have shown that Zeckendorf representations can be transfo
rmed to base $\\varphi$ expansions by a 2-tape automaton. I will take a di
rect approach: what are the words that can occur in the Zeckendorf represe
ntations\, and what are those that occur in base $\\varphi$ expansions? In
which representations/expansions\, of which natural numbers do they occur
?\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthieu Rosenfeld (LIS\, Marseille\, France)
DTSTART:20201026T140000Z
DTEND:20201026T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/9
DESCRIPTION:Title: A simple proof technique to study avoidability of repe
titions\nby Matthieu Rosenfeld (LIS\, Marseille\, France) as part of O
ne World Combinatorics on Words Seminar\n\n\nAbstract\nI recently describe
d a new proof technique that I used to study nonrepetitive colorings of gr
aphs. This technique is in fact more general and seems to be as powerful a
s the Lovász local lemma or the entropy compression method. For instance
\, it has since been used by D.R. Wood and I.M. Wanless in the context of
boolean satisfiability problem and of hypergraph colorings. In the partic
ular context of combinatorics on words similar approaches had already been
used by different authors\, but were never extended to graphs or other st
ructures.\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 ext
end this approach to nonrepetitive colorings of graphs of bounded degree.\
n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Eric Rowland (Hofstra University)
DTSTART:20201109T140000Z
DTEND:20201109T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/10
DESCRIPTION:Title: Avoiding fractional powers on an infinite alphabet\nby Eric Rowland (Hofstra University) as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nQuestions concerning avoidability of patt
erns have been central to combinatorics on words since the work of Thue. I
n 2009\, Guay-Paquet and Shallit gave several results about pattern avoida
nce of words on the alphabet of natural numbers. Most patterns are avoidab
le on this alphabet\, but it is interesting to ask about the lexicographic
ally least word that avoids a pattern. For fractional powers\, often this
word is generated by a relatively simple morphism. In recent work with Man
on Stipulanti\, we discovered the structure of the lexicographically least
5/4-power-free word on the natural numbers. In a surprising departure fro
m previously studied words\, the morphism generating this word does not pr
eserve 5/4-power-freeness.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Émilie Charlier (University of Liège)
DTSTART:20201123T140000Z
DTEND:20201123T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/11
DESCRIPTION:Title: Regular sequences in abstract numeration systems\
nby Émilie Charlier (University of Liège) as part of One World Combinato
rics on Words Seminar\n\n\nAbstract\nAn abstract numeration system $S$ is
given by a regular language $L$ over a totally ordered alphabet $(A\,<)$.
The numeration language $L$ is ordered thanks to the radix (or genealogica
l) order induced by $<$. A natural number $n$ is then represented by the $
n$-th word of the language (where we start counting from $n=0$). Integer b
ases $b$ and numeration systems based on a linear base sequence $U$ with a
regular numeration language are examples of abstract numeration systems.
The notion of $b$-regular sequences was extended to abstract numeration sy
stems by Maes and Rigo. Their definition is based on a notion of $S$-kerne
l that extends that of $b$-kernel. However\, this definition does not allo
w us to generalize all of the many characterizations of $b$-regular sequen
ces. In this talk\, I will present an alternative definition of $S$-kernel
\, and hence an alternative definition of $S$-regular sequences\, that per
mits us to use recognizable formal series in order to generalize most (if
not all) known characterizations of $b$-regular sequences. I will also sho
w that an extra characterization can be obtained in the case of Pisot nume
ration systems. Finally\, I will consider the special cases of $S$-automat
ic and $S$-synchronized sequences. In particular\, we will see that the fa
ctor complexity of an $S$-automatic sequence defines an $S$-regular sequen
ce. This is a joint work with Célia Cisternino and Manon Stipulanti.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marie Lejeune (University of Liège)
DTSTART:20201207T140000Z
DTEND:20201207T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/12
DESCRIPTION:Title: Reconstructing words from right-bounded-block words\nby Marie Lejeune (University of Liège) as part of One World Combinato
rics on Words Seminar\n\n\nAbstract\nIn this joint work with P. Fleischman
n\, F. Manea\, D. Nowotka\, and M. Rigo\, we study a variation of the famo
us reconstruction 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 va
riation of this problem.\nLet $\\mathcal{A}$ be a given alphabet and $n$ a
natural 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 o
f the type "What is the multiplicity of $u_i$ as subword of $w$?". Based o
n the answers to questions related to words $u_1\, \\ldots\, u_i$\, we can
decide which will be the next question (i.e. decide which word will be $u
_{i+1}$). We want to have the shortest sequence $(u_1\, \\ldots\, u_k)$ un
iquely determining $w$.\n\nWe naturally look for a value of $k$ less than
the upper known bound for $k$-reconstructibility.\n\nWe will show how to r
econstruct a binary word $w$ from $m+1$ questions\, where $m$ is the minim
um number of occurrences of {\\tt a} and {\\tt b} in the word. We then red
uce the problem for arbitrary finite alphabets to the binary case. We comp
are our bounds to the best known one for the classical reconstruction prob
lem.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sébastien Labbé (LaBRI\, Bordeaux\, France)
DTSTART:20201214T140000Z
DTEND:20201214T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/13
DESCRIPTION:Title: A characterization of Sturmian sequences by indisting
uishable asymptotic pairs\nby Sébastien Labbé (LaBRI\, Bordeaux\, Fr
ance) as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nW
e give a new characterization of Sturmian configurations in terms of indis
tinguishable asymptotic pairs. Two asymptotic configurations on a full $\\
mathbb{Z}$-shift are indistinguishable if the sets of occurrences of every
pattern in each configuration coincide up to a finitely supported permuta
tion. This characterization can be seen as an extension to biinfinite sequ
ences of Pirillo's theorem which characterizes Christoffel words. Furtherm
ore\, we provide a full characterization of indistinguishable asymptotic p
airs on arbitrary alphabets using substitutions and characteristic Sturmia
n sequences. The proof is based on the well-known notion of derived sequen
ces.\n\nThis is joint work with Sebastián Barbieri and Štěpán Starosta
. Preprint is available at https://arxiv.org/abs/2011.08112\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anna Frid (Aix-Marseille Université)
DTSTART:20210104T140000Z
DTEND:20210104T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/14
DESCRIPTION:Title: Is not prefix palindromic length of a k -automatic w
ord k -regular?\nby Anna Frid (Aix-Marseille Université) as part of
One World Combinatorics on Words Seminar\n\n\nAbstract\nWe consider the fu
nction of the prefix palindromic length for $k$-automatic words and prove
that it is $k$-regular for such words containing a finite number of distin
ct palindromes\, like for example the paperfolding word. We also observe t
hat in the opposite case\, if the number of distinct palindromes is infini
te\, this function can be $k$-regular\, as for the Thue-Morse word\, or se
emingly not\, as for the period-doubling word. The fact of non-regularity\
, however\, stays unproven.\n\nThis is a joint work with Enzo Laborde and
Jarkko Peltomäki.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean-Paul Allouche (CNRS\, IMJ-PRG\, Sorbonne Université\, Paris)
DTSTART:20210201T140000Z
DTEND:20210201T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/16
DESCRIPTION:Title: Hidden automatic sequences\nby Jean-Paul Allouche
(CNRS\, IMJ-PRG\, Sorbonne Université\, Paris) as part of One World Comb
inatorics on Words Seminar\n\n\nAbstract\nWe discuss a joint work with Mic
hel Dekking and Martine Queffélec (https://arxiv.org/abs/2010.00920) abou
t sequences given as fixed points of non-uniform morphisms that happen to
be actually automatic.\n\nOne of the most ancien example is probably the o
ne due to Berstel\, who proved that the Istrail squarefree sequence define
d as the 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 d
ue to M. Dekking at the end of the 70's\, we give several examples (in par
ticular of sequences in the OEIS). Finally we focus on morphisms associate
d with Grigorchuk(-like) groups.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Petr Ambrož
DTSTART:20210215T140000Z
DTEND:20210215T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/17
DESCRIPTION:Title: Morphisms generating antipalindromic words\nby Pe
tr Ambrož as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nWe introduce two classes of morphisms over the alphabet\n$A=\\{0\,1\\}
$ whose fixed\npoints contain infinitely many antipalindromic factors. An\
nantipalindrome is a finite word invariant\nunder the action of the antimo
rphism $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 m
orphisms (up to\nconjugation) which generate infinite words with\ninfinite
ly many antipalindromes. This is an analogue to the famous HKS\nconjecture
concerning infinite words\ncontaining infinitely many palindromes. We pro
ve our conjecture for two\nspecial classes of morphisms\,\nnamely (i) unif
orm morphisms and (ii) morphisms with fixed points\ncontaining also infini
tely many palindromes.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mickaël Postic
DTSTART:20210301T140000Z
DTEND:20210301T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/18
DESCRIPTION:Title: Open and closed complexity functions of infinite word
s\nby Mickaël Postic as part of One World Combinatorics on Words Semi
nar\n\n\nAbstract\nClosed words\, also known as complete first returns\, h
ave been studied for a long time\, and play an important role in symbolic
dynamics. A word which is not closed is said to be open. In this talk base
d on a joint work with Olga Parshina\, I will present a characterization o
f aperiodic words in terms of their open complexity function and closed co
mplexity function\, in the spirit of Morse and Hedlund's theorem. The prep
rint is available at https://arxiv.org/pdf/2005.06254.pdf\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Szymon Stankiewicz
DTSTART:20210315T140000Z
DTEND:20210315T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/19
DESCRIPTION:Title: Square-free reducts of words\nby Szymon Stankiewi
cz as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe d
iscuss a joint work with Jarosław Grytczuk (https://arxiv.org/abs/2011.12
822) about square-free reducts of words.\n\nIn any finite word one may del
ete the repeated block of a square\, obtaining thereby a shorter word. By
repeating 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 posit
ive integer $n$ there is a word over ternary alphabet which can be reduced
to at least $n$ different words and also that there is a word over alphab
et of size four which has exactly $n$ reducts. We will also show that ther
e exists infinitely many ternary words having exponential many reducts in
the length of these words.\n\nFor a fixed alphabet one can create a poset
with nodes being words and $u > v$ iff word $u$ can be reduced to word $v$
. We will describe some properties of those posets.\n
LOCATION:https://stable.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:20260404T110833Z
UID:CombinatoricsOnWords/20
DESCRIPTION:Title: From Fibonacci to golden mean representations\nby
Jacques Sakarovitch (RIF\, CNRS / Univ. de Paris and Télécom Paris\, IP
P) as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nEver
y positive integer can be written as a sum of Fibonacci numbers\; this yie
lds a Fibonacci representation of the integer. A positive integer can also
be written as a (finite) sum of (positive and negative) powers of the gol
den mean\; this yields a golden mean representation of the integer\, with
the radix point roughly in the middle of the writing. It is the golden mea
n expansion when it contains no consecutive digits equal to 1.\n\nWe show
that there exists a letter-to-letter finite two-tape automaton that maps t
he Fibonacci representation of any positive integer onto its golden mean e
xpansion\, provided the latter is folded around the radix point. As a coro
llary\, the set of golden mean expansions of the positive integers is a li
near context-free language.\n\nThese results are generalised to the more g
eneral case of integer representations in numeration systems built upon qu
adratic Pisot units.\n\nJoint work with Christiane Frougny\, published in
1999 in the Journal of Algebra and Computation. This talk is a follow-up t
o the one of October 15 by Michel Dekking\, who kindly quoted this paper b
ut deemed it hard to understand.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Valérie Goyheneche
DTSTART:20210412T130000Z
DTEND:20210412T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/21
DESCRIPTION:Title: Eigenvalues and constant arithmetical progressions fo
r substitutive sequences\nby Valérie Goyheneche as part of One World
Combinatorics on Words Seminar\n\n\nAbstract\nThe main subject of this tal
k is to answer the following decidability question : does a substitutive s
equence $x$ admit a constant arithmetical progression $(x_{k+np})_n$?\n\nO
ur method mainly relies on the link between constant arithmetical subseque
nces and (dynamical) eigenvalues of the underlying dynamical system.\nWe w
ill explain a method to compute the set of (additive) eigenvalues associat
ed to such systems.\nWe can then deduce\, given an integer $p$\, if the se
quence $x$ contains a constant arithmetical progression with period $p$.\n
At the end of the talk\, we will focus on the case of primitive constant-l
ength substitutions\, for which the set of such periods can be described b
y an automaton.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luca Zamboni
DTSTART:20210426T130000Z
DTEND:20210426T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/22
DESCRIPTION:Title: Singular words\nby Luca Zamboni as part of One Wo
rld Combinatorics on Words Seminar\n\n\nAbstract\nThe extremal solutions t
o certain problems in the theory of finite continued fractions are charact
erised by a special combinatorial property which we call the _singular_ pr
operty. This property may be interpreted in the framework of finite words\
, cyclic words\, and one and two-sided infinite words over arbitrary order
ed alphabets. Each linear (resp. cyclic) word w is Abelian equivalent to a
singular linear (resp. cyclic) word w’ which is in general unique up to
reversal. We develop an algorithm for generating all singular words havi
ng a prescribed Parikh vector which is based in part on a non-commutative
variant of the usual Euclidean algorithm. This allows us to answer a quest
ion of G. Ramharter from 1983 on the extremal values of the regular and se
mi-regular cyclic continuants introduced by Motzkin and Straus in the 1950
’s. We also confirm a conjecture of Ramharter in certain instances and e
xhibit counter examples in other cases. As for infinite words\, the singu
lar property in the context of bi-infinite binary words coincides with the
Markoff property which was shown by C. Reutenauer to be equivalent to the
balance property. We generalise this to higher alphabets by showing that
the singular property is the fundamental property which characterises th
e language structure of codings of symmetric k-interval exchange transform
ations. This is based on a collaboration with Alessandro De Luca and Marc
ia Edson initiated during the first Covid lockdown of 2020.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robert Mercas (Loughborough University)
DTSTART:20210208T140000Z
DTEND:20210208T150000Z
DTSTAMP:20260404T110833Z
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
Combinatorics on Words Seminar\n\n\nAbstract\nThe topic of counting the d
istinct 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 Fraenkel and Simpson in ’98\, who also showed that their number is u
pper bounded by twice the length of the word. However\, their conjecture t
hat the factor of 2 is superfluous (the length of the word is a strict bou
nd) is still open (though there exist several improvements of their origin
al result). Moreover\, recently Manea and Seki showed that proving the bou
nd for binary words is enough. Moreover\, further work was done on countin
g distinct repetitions of higher exponent with quite sharp bounds.\nBy loo
king at non-extendable repetitions of power at least two (thus considering
fractional ones as well) Kolpakov and Kucherov tried to bound in ‘99 th
e number of runs in a word (non-necessarily distinct). This was recently s
hown 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 sticki
ng point\, namely the three squares lemma of Crochemore and Rytter\, which
they all use as main tool. In this talk I will present a different techni
que (which so far is not fully exploited) of trying to count distinct squa
res and show some surprising connections between all of the above notions.
\n
LOCATION:https://stable.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:20260404T110833Z
UID:CombinatoricsOnWords/24
DESCRIPTION:Title: Day of short talks\nby M. Andrieu\, C. Cisterino\
, L. Dvořáková\, Š. Holub\, F. Manea\, C. Reutenauer as part of One Wo
rld Combinatorics on Words Seminar\n\n\nAbstract\n15:00 Christophe Reutena
uer An arithmetical characterization of Christoffel words\n\n15:30 Célia
Cisternino Two applications of the composition of a \n2-tape automaton and
a weighted automaton\n\n16:00 Lubka Dvořáková On balanced sequences wi
th the minimal asymptotic critical exponent\n\n16:30 Štěpán Holub Forma
lization of Combinatorics on Words in Isabelle/HOL\n\n17:00 Florin Manea E
fficiently Testing Simon's Congruence\n\n17:30 Mélodie Andrieu A Rauzy fr
actal unbounded in all directions of the plane\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Day of short talks
DTSTART:20210322T140000Z
DTEND:20210322T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/25
DESCRIPTION:Title: Day of short talks: I. Aedo\, F. Dolce\, A. Frid\, J.
Palacio\, J. Shallit\nby Day of short talks as part of One World Comb
inatorics on Words Seminar\n\n\nAbstract\n15:00 Jane D. Palacio\, Coverabl
e bi-infinite substitution shifts\n\n15:30 Ibai Aedo\, On long arithmetic
progressions in binary Morse-like words\n\n16:00 Francesco Dolce\, On morp
hisms preserving palindromic richness\n\n16:30 Jeffrey Shallit\, Robbins a
nd Ardila meet Berstel\n\n17:00 Anna E. Frid\, The semigroup of trimmed mo
rphisms\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwenaël Richomme
DTSTART:20210503T130000Z
DTEND:20210503T140000Z
DTSTAMP:20260404T110833Z
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
\nAbstract\nThe stable set associated to a given set $S$ of nonerasing end
omorphisms or substitutions is the set of all right infinite words that ca
n be indefinitely desubstituted over $S$. This notion generalizes the noti
on of sets of fixed points of morphisms. It is linked to $S$-adicity and t
o property preserving morphisms. Two main questions are considered. Which
known sets of infinite words are stable sets? Which ones are stable sets o
f a finite set of substitutions? While bringing answers to the previous qu
estions\, some new way of characterizing several well-known sets of words
such as the set of binary balanced words or the set of episturmian words a
re presented. A characterization of the set of nonerasing endomorphisms th
at preserve episturmian words is also provided.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kevin Buzzard
DTSTART:20210510T130000Z
DTEND:20210510T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/27
DESCRIPTION:Title: Teaching computers to prove theorems\nby Kevin Bu
zzard as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nO
ver the last few years I have been teaching proofs of theorems to computer
s\, and teaching students how to teach proofs of theorems to computers. Th
e Kruskal Katona theorem is a theorem I learnt as an MSc student\, and Cam
bridge 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 lin
es of theorem proofs\, many of them proved by mathematicians who have pick
ed up this language\, and most of them learnt it like Bhavik\, just choosi
ng a project and working on it. I will talk about how I learnt Lean\, how
you can learn Lean\, what the point of learning Lean is\, what the point o
f teaching Lean is\, and where all this stuff might end up going. Rest ass
ured -- I will not assume any prior familiarity with computer theorem pro
vers in this talk!\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeffrey Shallit
DTSTART:20210517T130000Z
DTEND:20210517T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/28
DESCRIPTION:Title: The Walnut Tutorial: Using A Tool for Doing Combinat
orics on Words\nby Jeffrey Shallit as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nWalnut is free open-source software\, writ
ten by Hamoon Mousavi\, that can\nrigorously prove or disprove claims abou
t automatic sequences (broadly\nunderstood)\, such as the Thue-Morse seque
nce\, the Fibonacci infinite\nword\, and others. It can also be used to c
reate explicit formulas for\nvarious aspects of such sequences\, such as s
ubword 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 kinds of things you can and can't do with it.\nWe'll "get our hands d
irty" and solve problems in real time.\n\nAt the end\, if there's time\, I
'll solicit problems about such sequences\nfrom the audience and try to so
lve them with Walnut. Come prepared with\nsome conjecture you haven't bee
n able to prove yet!\n\nThe tutorial will last about 90 minutes.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Etienne Moutot
DTSTART:20210531T130000Z
DTEND:20210531T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/29
DESCRIPTION:Title: Recent advances around Nivat's conjecture\nby Eti
enne Moutot as part of One World Combinatorics on Words Seminar\n\n\nAbstr
act\nNivat's conjecture states that any two dimensional word with "low eno
ugh" pattern complexity must be periodic.\nEven if the statement of the co
njecture is quite simple and very similar to the one dimensional Morse-Hed
lund theorem\, the conjecture is still open since stated by Maurice Nivat
in 1997. However\, there have been a lot of progress towards a proof in th
e last five years\, and many new tools started to emerge. In 2015\, Cyr an
d Kra started to use tools from symbolic dynamics to improve the bound req
uired to prove periodicity. At about the same time\, Jarkko Kari and Micha
l Szabados started to develop an algebraic approach to tackle the conjectu
re\, leading to very elegant proofs of new results related to Nivat's conj
ecture.\n\nIn this talk I will present the conjecture and some of the last
results around it. I will then focus on the algebraic approach initiated
by Kari and Szabados.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pascal Ochem
DTSTART:20210607T130000Z
DTEND:20210607T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/30
DESCRIPTION:Title: Avoiding large squares in trees and planar graphs
\nby Pascal Ochem as part of One World Combinatorics on Words Seminar\n\n\
nAbstract\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 graph class $C$\, $T(C)$ is the supremum of $T(G)$ over the graphs $G$
in $C$.\nThe Thue number has been investigated for famous minor-closed cla
sses:\n$T(tree) = 4$\, $7 \\leq T(outerplanar) \\leq 12$\, $11 \\leq T(p
lanar) \\leq 768$.\nFollowing a suggestion of Grytczuk\, we consider the g
eneralised parameters $T_k(C)$ such that only squares of period at least $
k$\nmust be avoided. Thus\, $T(C) = T_1(C)$.\nWe show that $T_2(tree) = 3$
\, $T_5(tree) = 2$\, and $T_k(planar) \\geq 11$ for every fixed $k$.\nThis
is a joint work with Daniel Gonçalves and Matthieu Rosenfeld.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Golnaz Badkobeh
DTSTART:20210614T130000Z
DTEND:20210614T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/31
DESCRIPTION:Title: Left Lyndon tree construction\nby Golnaz Badkobeh
as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe ext
end the left-to-right Lyndon factorisation of a word to the left Lyndon tr
ee construction of a Lyndon word. It yields an algorithm to sort the prefi
xes of a Lyndon word according to the infinite ordering defined by Dolce e
t 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://stable.researchseminars.org/talk/CombinatoricsOnWords/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Florin Manea
DTSTART:20210628T130000Z
DTEND:20210628T140000Z
DTSTAMP:20260404T110833Z
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\n
In this talk\, we will cover a series of recent algorithmic results relate
d to the processing of subsequences occurring in words. Firstly\, we will
show how to test in linear time whether two given words have exactly the s
ame 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 t
ime\, for two given words\, which is the largest positive integer $k$ for
which the two words are $k$-Simon-congruent. We will conclude this talk wi
th a series of related results. On the one hand\, we consider the problem
of transforming words by edit operations so that they become Simon-congrue
nt and\, on the other hand\, we consider the notion of absent subsequences
in words and problems related to this.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Štěpán Holub
DTSTART:20210712T130000Z
DTEND:20210712T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/33
DESCRIPTION:Title: Using Isabelle/HOL in Combinatorics on Words research
\nby Štěpán Holub as part of One World Combinatorics on Words Semin
ar\n\n\nAbstract\nIn this talk I will introduce a (growing) library of res
ults in Combinatorics on Words formalized in the proof assistant Isabelle/
HOL. I will emphasize the practical use of this library by a beginner\, ra
ther than theoretical aspects of either the proof assistant or the formali
zed results. The participants are therefore strongly encouraged to try Isa
belle along with me during my talk\, which requires to have Isabelle insta
lled\, as well as the draft version of our formalization downloaded. Quest
ions stemming from your own attempts are most welcome\, independently of h
ow naïve they may seem.\n\nFor an installation guide\, visit\nhttps://git
lab.com/formalcow/combinatorics-on-words-formalized#a-short-guide-for-isab
ellehol-beginners-how-to-formalize-your-combinatorics-on-words-result\nEve
rything should be straightforward. If you encounter any problem\, you can
write me to holub@karlin.mff.cuni.cz.\nIssues with the installation can be
also addressed during the preliminary technical session: I will be availa
ble 20 minutes before the official start.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jason Bell
DTSTART:20210726T130000Z
DTEND:20210726T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/34
DESCRIPTION:Title: Lie complexity of words\nby Jason Bell as part of
One World Combinatorics on Words Seminar\n\n\nAbstract\nGiven a right-inf
inite word $\\bf{w}$ over a finite alphabet\, we introduce a new complexit
y function $L_{\\bf w}(n)$\, motivated by the theory of Lie algebras\, who
se value 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 again a factor of ${\\bf w}$\, where two words $x$ and $y$ are equiv
alent if there exist words $a$ and $b$ such that $x=ab$ and $y=ba$. We sh
ow that the Lie complexity function is uniformly bounded for words ${\\bf
w}$ of linear factor complexity and that it is a $k$-automatic sequence wh
en ${\\bf w}$ is $k$-automatic. As a consequence of these results we can
show that if ${\\bf w}$ is a word of linear factor complexity then there a
re only finitely many primitive factors $v$ of ${\\bf w}$ with the propert
y that $v^n$ is a factor of ${\\bf w}$ for every $n\\ge 1$. We also consi
der extensions of these results. This is joint work with Jeffrey Shallit.
\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Day of Short Talks
DTSTART:20210621T130000Z
DTEND:20210621T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/35
DESCRIPTION:Title: Jakub Byszewski\, Jarosław Duda\, Jarkko Peltomäki\
, Palak Pandoh\, Clément Lagisquet\, Bartłomiej Pawlik\nby Day of Sh
ort Talks as part of One World Combinatorics on Words Seminar\n\n\nAbstrac
t\n15:00 Jakub Byszewski\, Automata and finite order automorphisms of the
power series ring\n\n15:30 Jarosław Duda\, Generalized Fibonacci coding p
roblem using Maximal Entropy Random Walk and Asymmetric Numeral Systems\n\
n16:00 Jarkko Peltomäki\, Initial nonrepetitive complexity of regular epi
sturmian words and their Diophantine exponents\n\n16:30 Palak Pandoh\, Cou
nting scattered palindromes in a finite word\n\n17:00 Clément Lagisquet\,
(LAMA) On Markov Numbers: An answer to three conjectures from Aigner\n\n1
7:30 Bartłomiej Pawlik\, Nonchalant procedure\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Arseny Shur
DTSTART:20210927T130000Z
DTEND:20210927T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/36
DESCRIPTION:Title: Abelian repetition threshold revisited\nby Arseny
Shur as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA
belian repetition threshold ART$(k)$ is the number separating fractional A
belian powers which are avoidable and unavoidable over the $k$-letter alph
abet. In contrast with the «usual» repetition threshold RT$(k)$\, no exa
ct values of ART$(k)$ are known. The lower bounds were proved in [A.V. Sam
sonov\, A.M. Shur. On Abelian repetition threshold. RAIRO ITA\, 2012] and
conjectured to be tight. We present a method of study of Abelian power-fre
e languages using random walks in prefix trees and some experimental resul
ts obtained by this method. On the base of these results\, we conjecture t
hat the lower bounds for ART$(k)$ by Samsonov and Shur are not tight for a
ll $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://stable.researchseminars.org/talk/CombinatoricsOnWords/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:France Gheeraert
DTSTART:20211011T130000Z
DTEND:20211011T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/37
DESCRIPTION:Title: $S$-adic characterization of dendric languages: terna
ry case\nby France Gheeraert as part of One World Combinatorics on Wor
ds Seminar\n\n\nAbstract\nUniformly recurrent dendric languages generalize
Arnoux-Rauzy languages and interval exchanges and are defined via the lef
t-\, right- and biextensions of their words. In a series of articles\, Ber
thé et al. introduced them and\, among other results\, proved that this f
amily is stable under derivation\, which leads to the existence of particu
lar $S$-adic representations.\n\nIn this talk\, we will see how we can use
the properties of these representations to obtain an $S$-adic characteriz
ation of uniformly recurrent dendric languages. We give some general resul
ts then focus on the case of a ternary alphabet to obtain a simpler charac
terization.\n\nThis is a joint work with Marie Lejeune and Julien Leroy.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fabien Durand
DTSTART:20211025T130000Z
DTEND:20211025T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/38
DESCRIPTION:Title: Beyond substitutive sequences : Self-induced dynamica
l systems and sequences on compact alphabets\nby Fabien Durand as part
of One World Combinatorics on Words Seminar\n\n\nAbstract\nIt is well-kno
wn that primitive substitutions are recognizable. This property implies th
at 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 iso
morphic to $(X\,S)$\, where $S_U (x)=S^n (x)$ and $n>0$ is the first itera
te coming 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 vi
ew self induction characterizes minimal substitution subshifts on possibly
infinite alphabets (even uncountable).\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dan Rust
DTSTART:20211108T140000Z
DTEND:20211108T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/39
DESCRIPTION:Title: Random substitutions\nby Dan Rust as part of One
World Combinatorics on Words Seminar\n\n\nAbstract\nA random substitution
is a generalisation of a substitution on a finite alphabet. Whereas with c
lassical substitutions\, letters have a single word as an image\, random s
ubstitutions have a finite set of possible image words that are independen
tly chosen each time it is applied to the letters in a word. As an example
\, the `random Fibonacci substitution' is given by\n\n$$ a \\mapsto \\{ab\
,ba\\}\, b \\mapsto \\{a\\}.$$\n\nThis gives rise to languages of legal wo
rds that share similar properties with substitutive words (i.e.\, hierarch
ical structures) but which also have exponential complexity functions (ent
ropy). 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-sta
te open problems.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Day of short talks
DTSTART:20211122T140000Z
DTEND:20211122T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/40
DESCRIPTION:Title: G. Kucherov\, J. O. Shallit\, J: Grytczuk\, D. Gabric
\nby Day of short talks as part of One World Combinatorics on Words Se
minar\n\n\nAbstract\n15:00 Gregory Kucherov\, Minimizers and one question
about de Bruijn graphs\n15:30 Jeffrey O. Shallit\, Abelian cubes and addit
ive cubes in the Tribonacci word\n15:45 Jarosław Grytczuk\, Twins in perm
utations\n16:15 Daniel Gabric\, Words that almost commute\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gabriele Fici
DTSTART:20211206T140000Z
DTEND:20211206T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/41
DESCRIPTION:Title: Some Remarks on Automatic Sequences\, Toeplitz words
and Perfect Shuffling\nby Gabriele Fici as part of One World Combinato
rics on Words Seminar\n\n\nAbstract\nOne of the many nice properties of th
e Thue-Morse sequence $t = 0110100110010110\\cdots$ is that t is equal to
the perfect shuffling of itself with its binary complement $(1-t)$\, i.e.\
, it can be defined by means of the equation $t = t ⧢ (1 − t)$. In ge
neral\, for any automatic sequence $w$\, there exist two automatic sequenc
es $w'$ and $w’’$ such that $w = w' ⧢ w''$. We call the sequences $
w’$ and $w’’$ the even and the odd part of $w$\, respectively. We wi
ll exhibit some curious facts about this decomposition for some (more or l
ess) known 2- and 3-automatic sequences.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jakub Konieczny
DTSTART:20211220T140000Z
DTEND:20211220T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/42
DESCRIPTION:Title: Finitely-valued generalised polynomials\nby Jakub
Konieczny as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nGeneralised polynomials are expressions constructed from polynomials w
ith the use of the floor function\, addition and multiplication\, such as
$\\lfloor \\sqrt{2} n \\lfloor \\sqrt{3} n^2\\rfloor + \\sqrt{6} + \\frac{
1}{2}\\rfloor$. Despite superficial similarity\, generalised polynomials e
xhibit many phenomena which are impossible for ordinary polynomials. In pa
rticular\, there exist generalised polynomial sequences which take only fi
nitely many values but are not constant. This is the case\, for instance\,
for Sturmian sequences.\n\nIn my talk\, I will discuss finitely-valued ge
neralised polynomial sequences from the perspective of combinatorics on wo
rds. The talk will include a survey of existing results on generalised pol
ynomials\, adapted to the current context\, as well as several new results
obtained in joint works with Boris Adamczewski and with Jakub Byszewski.\
n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lubomíra Dvořáková
DTSTART:20220110T140000Z
DTEND:20220110T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/43
DESCRIPTION:Title: On minimal critical exponent of balanced sequences\nby Lubomíra Dvořáková as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nThe conjecture stated by Rampersad\, Shallit and Van
domme says that the minimal critical exponent of balanced sequences over t
he alphabet of size $d>4$ equals $(d-2)/(d-3)$. This conjecture is known t
o hold for $d=5\, 6\, 7\, 8\, 9\, 10$. \n\nIn this talk\, we will describe
in more details the ideas and the techniques used to refute this conjectu
re by showing that the picture is different for bigger alphabets. We prove
that critical exponents of balanced sequences over an alphabet of size $d
>10$ are lower bounded by $(d-1)/(d-2)$ and this bound is attained for al
l even numbers $d>10$. \n\nAccording to this result\, we conjecture that t
he least critical exponent of a balanced sequence over $d$ letters is $(d-
1)/(d-2)$ for all $d>10$.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Markus Whiteland
DTSTART:20220124T140000Z
DTEND:20220124T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/44
DESCRIPTION:Title: On some decidable properties of discrete-time linear
dynamical systems\nby Markus Whiteland as part of One World Combinator
ics on Words Seminar\n\n\nAbstract\nA discrete-time linear dynamical syste
m (LDS) $(A\,x)$ is the orbit of a point $x \\in \\mathbb{R}^d$ under a li
near map $A\\colon \\mathbb{R}^d \\to \\mathbb{R}^d$. In this talk we cons
ider decision problems on LDS arising from program verification\, such as
reachability problems: given a LDS $(A\,x)$ and a semi-algebraic target se
t $T \\in \\mathbb{R}^d$\, does the orbit intersect $T$? It is well-known
that such questions quickly lead to open problems\, such as Skolem's probl
em on linear recurrence sequences. We identify the borderline between hard
instances and decidable instances with respect to the dimension of the ta
rget set $T$. The methods used in the decidable cases quickly give rise to
symbolic dynamical systems over which we have a lot of control: this allo
ws us to go beyond mere reachability to deciding $\\omega$-regular propert
ies of the LDS with respect to a low-dimensional target set $T$.\n\nJoint
work with C. Baier\, F. Funke\, S. Jantsch\, T. Karimov\, E. Lefaucheux\,
F. Luca\, J. Ouaknine\, D. Purser\, A. Varonka\, and J. Worrell.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Dekking
DTSTART:20220207T140000Z
DTEND:20220207T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/45
DESCRIPTION:Title: Combinatorics of Fibonacci and golden mean number rep
resentations\nby Michel Dekking as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nHow many ways are there to represent a number
as a sum 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 F
ibonacci numbers?\n\nI will give some answers to these questions in my tal
k.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean-Paul Allouche
DTSTART:20220307T140000Z
DTEND:20220307T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/46
DESCRIPTION:Title: Thue and 7-3\nby Jean-Paul Allouche as part of On
e World Combinatorics on Words Seminar\n\n\nAbstract\nMarch 7\, 2022 (in F
rench 7/3) is the 100th anniversary of the death of Axel Thue. He was a No
rwegian mathematician\, principally known for his work in Diophantine appr
oximation\, 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 contri
bution in combinatorics\, essentially restricting ourselves to the –ubiq
uitous– Thue-Morse or Prouhet-Thue-Morse sequence. We will try to survey
not only some well-known features of this sequence\, but also less classi
cal properties: one of these is an occurrence of… 7/3 for this sequence\
, the other is about Shogi (将棋)\, or Japanese chess\, and the Sennichi
te (千日手) (a new rule decided after a play dated March… 8\, 1983).\
n\nTo conclude this abstract\, we do not resist to give a quote of Thue:
“The further removed from usefulness or practical application\, the more
important.” Removed from practical application? one might want to look
at the definition of the programming language “Thue” that Wikipedia de
scribes as follows: “Thue is an esoteric programming language invented b
y John Colagioia in early 2000. It is a meta-language that can be used to
define or recognize Type-0 languages from the Chomsky hierarchy. Because i
t is able to define languages of such complexity\, it is also Turing-compl
ete itself. Thue is based on a nondeterministic string rewriting system ca
lled semi-Thue grammar\, which itself is named after the Norwegian mathema
tician Axel Thue.”\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Narad Rampersad
DTSTART:20220321T130000Z
DTEND:20220321T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/47
DESCRIPTION:Title: Applications of Walnut to problems of local periodici
ty\nby Narad Rampersad as part of One World Combinatorics on Words Sem
inar\n\n\nAbstract\nThere are a number of natural choices for measuring th
e local\nperiodicity at a given position $i$ of an infinite word: for inst
ance\,\none could consider repetitions 1) ending at position $i$\; 2) star
ting\nat position $i$\; or 3) centered at position $i$. With regards to\n
option 1)\, it is known that aperiodic infinite words cannot have all\nsuf
ficiently large prefixes end with cubes. It is natural then to ask\nfor s
uch words how many prefixes can end with cubes. Using Walnut\, we\nobtain
a characterization of these prefixes for the Fibonacci word.\nRegarding o
ption 3)\, Mignosi and Restivo introduced an interesting\ncomplexity measu
re: $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
asymptotic behaviour of this function for some\n2-automatic sequences\, su
ch as the Thue-Morse sequence\, the\nRudin-Shapiro sequence\, and the peri
od-doubling sequence.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Etienne Moutot
DTSTART:20220221T140000Z
DTEND:20220221T150000Z
DTSTAMP:20260404T110833Z
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\nAb
stract\nIn this presentation\, I will talk about pattern complexity of two
-dimensional substitutive shifts. More precisely\, I will focus on lower b
ounds on the complexity of {\\bf aperiodic} 2D substitutive shifts.\n\n{\\
it Pattern complexity} consists in counting the number of different mxn re
ctangular patterns that appear in an infinite coloring of $\\mathbb Z^2$ o
r in a shift space. A corollary of our recent work with Jarkko Kari on Niv
at's conjecture [1] shows that any aperiodic subshift have pattern complex
ity at least $mn+1$ for all $m$ and $n$.\n\nWith Coline Petit-Jean we have
been trying to improve this lower bound for a particular class of shift s
paces: substitutive shifts. For some substitutions ({\\it primitive} and {
\\it marked} substitutions)\, we show that if their shift space is aperiod
ic\, then it has complexity at least $C*mn$\, with $C>1$ a constant depend
ing on the substitution. I will also talk briefly about non-marked substit
utions and why our current proof does not apply to them\, even if we belie
ve that a similar result might still hold.\n\n[1] Decidability and Periodi
city of Low Complexity Tilings. Jarkko Kari\, Etienne Moutot\, Theory of C
omputing Systems\, 2021\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Moussa Barro
DTSTART:20220516T130000Z
DTEND:20220516T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/49
DESCRIPTION:Title: Billard dans le cube\nby Moussa Barro as part of
One World Combinatorics on Words Seminar\n\n\nAbstract\nOn considère le b
illard dans un cube. On code une trajectoire par les faces rencontrées. L
e but de l'exposé sera de décrire le langage d'un tel mot dans le cas ou
l'orbite n'est pas dense.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Colin Defant
DTSTART:20220404T130000Z
DTEND:20220404T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/50
DESCRIPTION:Title: Anti-powers in Aperiodic Recurrent Words\nby Coli
n Defant as part of One World Combinatorics on Words Seminar\n\n\nAbstract
\nIn 2016\, Fici\, Restivo\, Silva\, and Zamboni introduced the notion of
a $k$-anti-power\, which is a word of the form $w_1 \\cdots w_k$\, where $
w_1\,\\ldots\,w_k$ are words of the same length that are all distinct. I w
ill begin by reviewing the main results that these authors proved about an
ti-powers. I will then discuss anti-powers appearing as factors in the Thu
e-Morse word. This will lead into a discussion of anti-powers in aperiodic
recurrent words and aperiodic morphic words.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christophe Reutenauer
DTSTART:20220425T130000Z
DTEND:20220425T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/51
DESCRIPTION:Title: Constructions and parametrization of conjugates of Ch
ristoffel words\nby Christophe Reutenauer as part of One World Combina
torics on Words Seminar\n\n\nAbstract\nFollowing a recent work of Michel L
aurent and the first author\, we propose a deformation of the Rauzy rules
(equivalently of the de Luca construction of standard words) in order to c
onstruct all conjugates of all Christoffel words (equivalently of all stan
dard words). This construction is based on integer legal Ostrowski represe
ntations\, following Frid. The constructed word depends only the represent
ed integer (and even works in the free group\, up to conjugation however).
Choosing greedy representations\, we determine of the longest border of c
onjugates\, thereby recovering results of Lapointe on the smallest periods
. Choosing the lazy representation\, we may revisit the Sturmian graph of
Epifanio\, Frougny\, Gabriele\, Mignosi and Shallit\; in particular we sho
w that this graph is essentially a subgraph of the Stern-Brocot tree\, and
that the compact graph (which is a compaction of the minimal automaton of
the set of suffixes of a central word) is similarly embedded in the tree
of central words of Aldo de Luca.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre-Adrien Tahay
DTSTART:20220530T130000Z
DTEND:20220530T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/52
DESCRIPTION:Title: Column representation of words in cellular automata\nby Pierre-Adrien Tahay as part of One World Combinatorics on Words Sem
inar\n\n\nAbstract\nThe task of representing a sequence over a finite alph
abet in the space-time\ndiagram of a cellular automaton is a non-trivial a
nd still not entirely explored\ntopic. One of the first results on the sub
ject was done by Fischer in 1965 with a construction of the characteristic
sequence of primes numbers. Many results and improvements have been estab
lished since. In 2015\, Rowland and Yassawi showed that there is a close c
onnection between the $p$-automatic sequences and the linear cellular auto
mata. More precisly the columns of linear cellular automata are $p$-\nauto
matic sequences and all $p$-automatic sequences can be realized by some li
near cellular automata with memory. Moreover their proof is constructive.
In 2018\, Marcovici\, Stoll and Tahay investigated some constructions for
nonautomatic sequences such as the characteristic sequences of polynomials
and the Fibonacci word.\n\nIn this talk I will present recent results obt
ained in collaboration with Francesco Dolce where we generalized the const
ruction for the Fibonacci word in a column of a cellular automaton\, to an
y Sturmian word with quadratic slope. Our proof is constructive and use th
e ultimate periodicity of the continued fraction expansion of the slope of
the word.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kristina Ago and Bojan Bašić
DTSTART:20220613T130000Z
DTEND:20220613T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/53
DESCRIPTION:Title: Some recent results on two "palindromicity" measures<
/a>\nby Kristina Ago and Bojan Bašić as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nVarious measures of the degree of "palindr
omicity" of a given word have been defined in the literature. In this talk
we present some of our results concerning two such measures. The first on
e is the so-called \\emph{palindromic defect} (or only \\emph{defect}). Le
t $|\\mathrm{Pal}(w)|$ denote the number of palindromic factors of a word
$w$. The palindromic defect of $w$ is defined by $|w|+1-|\\mathrm{Pal}(w)|
$ (it can be proved that this value is always nonnegative). This definitio
n can be naturally extended to infinite words. While infinite words whose
defect is zero (called \\emph{rich}) have been researched quite much\, the
re are noticeably less results in the literature on infinite words of fini
te positive defect. In the first part of the talk we introduce a construct
ion of an infinite family of infinite words whose defect is finite and in
many cases positive (with fully characterized cases when the defect is $0$
)\, and we analyze their properties. Each of those words is either periodi
c (which is a less interesting case\, and explicitly characterized)\, or r
ecurrent but not uniformly recurrent. Examples of explicit constructions o
f such words that are not uniformly recurrent have been quite deficient in
the literature so far.\n\nThe second part of talk is devoted to the so-ca
lled \\emph{MP-ratio}. The concept of MP-ratio is based on palindromic sub
words (and not factors) of a given finite word. Call a word over an $n$-ar
y alphabet \\emph{minimal-palindromic} if it does not contain palindromic
subwords of length greater than $\\big\\lceil\\frac{|w|}n\\big\\rceil$. Th
e \\emph{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 minimal-palindromic and that the length $|r|+|s|$ is minimal possible
. In order for the MP-ratio to be well-defined\, it has to be shown that s
uch a pair $(r\,s)$ always exist. It has been known for some time that thi
s is true in the binary case\, but this question becomes much more complic
ated for larger arities. In this talk we show that the MP-ratio is well-de
fined for any arity\, and we present some further results on this topic.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Antoine Domenech
DTSTART:20220620T130000Z
DTEND:20220620T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/54
DESCRIPTION:Title: Avoiding doubled patterns\nby Antoine Domenech as
part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA pattern
$P$ is $k$-avoidable if there exists\nan infinite word over $k$ letters t
hat contains no occurrence of $P$.\nA pattern is doubled if all its variab
les appear at least twice.\nIt is known that doubled patterns are 3-avoida
ble and it is conjectured\nthat only a finite number of doubled patterns a
re not 2-avoidable.\nWe show that square-free doubled patterns with at mos
t 4 variables are 2-avoidable.\nThen\, for each pattern doubled $P$ with a
t most 3 variables that is\nnot 2-avoidable\, we determine the minimum num
ber of distinct\noccurrences of $P$ that are contained in an infinite bina
ry word.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre Popoli
DTSTART:20220627T130000Z
DTEND:20220627T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/55
DESCRIPTION:Title: Maximum order complexity for some automatic and morph
ic sequences along polynomial values\nby Pierre Popoli as part of One
World Combinatorics on Words Seminar\n\n\nAbstract\nAutomatic sequences ar
e not suitable sequences for cryptographic\napplications since both their
subword complexity and their expansion\ncomplexity are small\, and their c
orrelation measure of order 2 is\nlarge. These sequences are highly predic
table despite having a large\nmaximum order complexity. However\, recent r
esults show that polynomial\nsubsequences of automatic sequences\, such as
the Thue-Morse sequence\nor the Rudin-Shapiro sequence\, are better candi
dates for pseudorandom\nsequences. A natural generalization of automatic s
equences are morphic\nsequences\, given by a fixed point of a prolongeable
morphism that is\nnot necessarily uniform. In this talk\, I will present
my results on\nlowers bounds for the maximum order complexity of the Thue-
Morse\nsequence\, the Rudin-Shapiro sequence and the sum of digits functio
n in\nZeckendorf base\, which are respectively automatics and morphic\nseq
uences.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zachary Chase
DTSTART:20220711T130000Z
DTEND:20220711T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/56
DESCRIPTION:Title: The separating words\, $k$-deck\, and trace reconstru
ction problems\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
separate two\ngiven strings of length $n$? Can two distinct strings of len
gth $n$ have\nthe same multiset of subsequences of length $n^{1/3}$? How m
any random\nsubsequences of length $n/2$ of an unknown string $x$ of lengt
h $n$ do you\nneed to determine $x$ with high probability? We discuss thes
e three\nproblems\, each having an exponential gap between the best known
upper\nand lower bounds\, and touch upon how they might be more related th
an\none might expect.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shuo Li
DTSTART:20220919T130000Z
DTEND:20220919T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/57
DESCRIPTION:Title: On the number of squares in a finite word\nby Shu
o Li as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA
conjecture of Fraenkel and Simpson states that the number of distinct squa
res in a finite word $w$\n is bounded by its length. In this talk\, we wil
l review this conjecture from the perspective of the topological propertie
s of the Rauzy graphs of $w$. We prove this conjecture by giving a stronge
r statement: the number of distinct squares in a finite word \n$w$ is bou
nded by the length of $w$ minus the number of distinct letters in $w$.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/57/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robbert Fokkink
DTSTART:20221003T130000Z
DTEND:20221003T140000Z
DTSTAMP:20260404T110833Z
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 co
mbinatorial game involves a set of positions that are either won or lost f
or the player that moves next. These are the so-called N-positions. If you
know the set of N-positions\, then you have solved the game. Members of o
ur community will immediately wonder if the characteristic sequence of the
set of N-positions form a word. It turns out that Fibonacci word gives th
e set of N-positions in Wythoff Nim. Eric Duchene and Michel Rigo found ot
her examples of impartial games that are given by words\, initiating ongoi
ng work on the link between words and games. In this talk I will show how
a modification of Wythoff Nim can be described by the Tribonacci word. Thi
s is joint work with Dan Rust and Cisco Ortega.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/58/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Giuseppe Romana
DTSTART:20221017T130000Z
DTEND:20221017T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/59
DESCRIPTION:Title: String Attractor: a Combinatorial object from Data Co
mpression\nby Giuseppe Romana as part of One World Combinatorics on Wo
rds Seminar\n\n\nAbstract\nVery recently\, Kempa and Prezza [STOC 2018] in
troduced the notion of String Attractor in the field of Data Compression\,
and showed how this concept was already implicit in many other well known
compression schemes.\nBasically\, a String Attractor $\\Gamma$ of a finit
e word $w$ is a set of positions in $w$ such that each distinct factors th
at occurs in $w$ has at least an occurrence that crosses a position $j \\i
n \\Gamma$. \nIn this talk\, we explore String Attractors from a combinato
rial perspective.\nWe discuss how the size $\\gamma^*$ of a string attract
or of minimum size is affected when some classical combinatorial operation
s are applied to finite words.\nFurther\, we show how the size and other s
tructural properties of string attractors can be used to obtain new charac
terizations for infinite words.\nMost of the results presented in this tal
k come from [A combinatorial view on string attractors\, Theoret. Comput.
Sci. 2021] and [String Attractors and Infinite Words\, LATIN 2022] (to app
ear).\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/59/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Krenn
DTSTART:20221107T140000Z
DTEND:20221107T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/60
DESCRIPTION:Title: $q$-Recursive Sequences and their Asymptotic Analysis
\nby Daniel Krenn as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nIn this talk\, we consider Stern’s diatomic sequence\, th
e number of\nnon-zero elements in some generalized Pascal's triangle and t
he number\nof unbordered factors in the Thue-Morse sequence as running exa
mples.\nAll these sequences can be defined recursively and lead to the con
cept\nof so-called $q$-recursive sequences. Here $q$ is an integer and at
least $2$\,\nand $q$-recursive sequences are sequences which satisfy a spe
cific type of\nrecurrence relation: Roughly speaking\, every subsequence w
hose indices\nrun through a residue class modulo $q^M$ is a linear combina
tion of\nsubsequences where for each of these subsequences\, the indices r
un\nthrough a residue class modulo $q^m$ for some $m < M$.\n\nIt turns out
that this property is quite natural and many combinatorial\nsequences are
in fact $q$-recursive. We will see that $q$-recursive\nsequences are rela
ted to $q$-regular sequences and a $q$-linear\nrepresentation of a sequenc
e can be computed easily. Our main focus is the asymptotic\nbehavior of th
e summatory functions of $q$-recursive sequences. Beside\ngeneral results\
, we present a precise asymptotic analysis of our three examples. For the
first two sequences\, our analysis even leads to\nprecise formulae without
error terms.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/60/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sebastián Barbieri
DTSTART:20221121T140000Z
DTEND:20221121T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/61
DESCRIPTION:Title: Indistinguishable asymptotic pairs\nby Sebastián
Barbieri as part of One World Combinatorics on Words Seminar\n\n\nAbstrac
t\nWe say two bi-infinite words are asymptotic if they differ in finitely
many coordinates. We say they are indistinguishable if for any finite word
w\, the 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 that they are very closely related to Sturmian configurations. We wil
l also show that a higher-dimensional analogue of the theorem holds\, and
as an application of this result we will provide a formula for computing t
he complexity of a multidimensional Sturmian configuration on any finite c
onnected support. This is joint work with S. Labbé.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/61/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Josef Rukavicka
DTSTART:20221205T140000Z
DTEND:20221205T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/62
DESCRIPTION:Title: Palindromic factorization of rich words\nby Josef
Rukavicka as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nA finite word $w$ is called rich if it contains $\\vert w\\vert+1$ dis
tinct palindromic factors including the empty word. For every finite rich
word $w$ there are distinct nonempty palindromes $w_1\, w_2\,\\dots\,w_p$
such that $w=w_pw_{p-1}\\cdots w_1$ and $w_i$ is the longest palindromic s
uffix of $w_pw_{p-1}\\cdots w_i$\, where $1\\leq i\\leq p$. This palindrom
ic factorization is called UPS-factorization. Let $luf(w)=p$ be the length
of UPS-factorization of $w$.\n\nIn 2017\, it was proved that there is a c
onstant $c$ such that if $w$ is a finite rich word and $n=\\vert w\\vert$
then $luf(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 alphabet.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/62/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jason Bell
DTSTART:20221219T140000Z
DTEND:20221219T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/63
DESCRIPTION:Title: Noncommutative rational Pólya series\nby Jason B
ell as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA P
ólya series over a field $K$ is a formal noncommutative power series whos
e nonzero coefficients are contained in a finitely generated subgroup of t
he multiplicative group of $K$. A complete description of such one-variabl
e series was given by Pólya\, and an extension to general noncommutative
rational series in terms of unambiguous weight automaton was later conject
ured by Reutenauer. We explain how to prove Reutenauer’s conjecture and
discuss certain decidability aspects of our work. This is joint work wit
h Daniel Smertnig.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/63/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pamela Fleischmann
DTSTART:20230109T140000Z
DTEND:20230109T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/64
DESCRIPTION:Title: $m$-Nearly $k$-Universal Words - Investigating Simon
Congruence\nby Pamela Fleischmann as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nDetermining the index of the Simon congrue
nce is a long outstanding open problem. Two words $u$ and $v$ are called S
imon congruent if they have the same set of scattered factors\, which are
parts of the word in the correct order but not necessarily consecutive\, e
.g.\, oath is a scattered factor of logarithm. Following the idea of scatt
ered factor $k$-universality\, we investigate $m$-nearly $k$-universality\
, i.e.\, words where $m$ scattered factors of length $k$ are absent\, w.r.
t. Simon congruence. We present a full characterisation as well as the ind
ex of the congruence for $m = 1$\, $2$\, and $3$. Moreover\, we present a
characterisation of the universality of repetitions.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/64/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Natalie Behague
DTSTART:20221024T130000Z
DTEND:20221024T140000Z
DTSTAMP:20260404T110833Z
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\nA
bstract\nAn automaton consists of a finite set of states and a collection
of functions from the set of states to itself. An automaton is synchronizi
ng if there is a word (that is\, a sequence of functions) that maps all st
ates onto the same state. Černý’s conjecture on the length of the shor
test such word is one of the most famous open problem in automata theory.
We considered the closely related question of determining the minimum leng
th of a word that maps some k states onto a single state.\n\nFor synchroni
zing automata\, we found a simple argument for general k almost halving th
e 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 wor
d sending 4 states to a singleton from $0.5n^2$ to $≈ 0.459n^2$\, and th
e minimum 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://stable.researchseminars.org/talk/CombinatoricsOnWords/65/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lubomíra Dvořáková
DTSTART:20230123T140000Z
DTEND:20230123T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/66
DESCRIPTION:Title: Essential difference between the repetitive thereshol
d and asymptotic repetitive threshold of balanced sequences\nby Lubom
íra Dvořáková as part of One World Combinatorics on Words Seminar\n\n\
nAbstract\nAt first\, we will summarize both the history and the state of
the art of the critical exponent and the asymptotic critical exponent of b
alanced sequences. \nSecond\, we will colour the Fibonacci sequence by sui
table constant gap sequences to provide an upper bound on the asymptotic r
epetitive threshold of $d$-ary balanced sequences. The bound is attained f
or $d$ equal to $2$\, $4$ and $8$ and we conjecture that it happens for in
finitely many even $d$'s. \nFinally\, we will reveal an essential differe
nce in behavior of the repetitive threshold and the asymptotic repetitive
threshold of balanced sequences: The repetitive threshold of $d$-ary bal
anced sequences is known to be at least $1+1/(d-2)$ for each $d$ larger t
han two. In contrast\, our bound implies that the asymptotic repetitive th
reshold of $d$-ary balanced sequences is at most $1+\\phi^3/2^{d-3}$ for e
ach $d$ larger than one\, where $\\phi$ is the golden mean. \n\nJoint wor
k with Edita Pelantová.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/66/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aline Parreau and Eric Duchêne
DTSTART:20230227T140000Z
DTEND:20230227T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/67
DESCRIPTION:Title: Taking and merging games as rewrite games\nby Ali
ne Parreau and Eric Duchêne as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nIn this talk\, we present some of the links between
combinatorial games and language theory. A combinatorial game is a 2-playe
r game with no chance and with perfect information. Amongst them\, the fam
ily of heap games such as the game of Nim\, subtraction or octal games bel
ong to the the most studied ones. Generally\, the analysis of such games c
onsist in determining which player has a winning strategy. We will first s
ee how this question is investigated in the case of heap games.\n\nIn a se
cond part of the talk\, we will present a generalization of heap games as
rewrite games on words. This model was introduced by Waldmann in 2002. Giv
en a finite alphabet and a set of rewriting rules on it\, starting from a
finite word w\, each player alternately applies a rule on w. The first pla
yer unable to apply a rule loses the game. In this context\, the main ques
tion is now about the class of the language formed by the losing and winni
ng positions of the game. For example\, for octal games that are solved in
polynomial time\, the losing positions form a rational language. By using
the model of rewrite games\, we will investigate here a new family of hea
p games that consist in merging heaps of tokens\, and consider some of the
different classes of languages that may emerge according to the rules of
the game.\n\nJoint work with V. Marsault and M. Rigo.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/67/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Konefal
DTSTART:20230206T140000Z
DTEND:20230206T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/68
DESCRIPTION:Title: Examining the Class of Formal Languages which are Exp
ressible via Word Equations\nby Matthew Konefal as part of One World C
ombinatorics on Words Seminar\n\n\nAbstract\nA word equation can be said t
o express a formal language via each variable occurring in it. The class W
E of formal languages which can be expressed in this way is not well under
stood. I will discuss a number of necessary and sufficient conditions for
a formal language L to belong to WE. I will give particular focus to the
case in which L is regular\, and to the case in which L is a submonoid.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/68/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Léo Poirier and Wolfgang Steiner
DTSTART:20230306T140000Z
DTEND:20230306T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/69
DESCRIPTION:Title: Factor-balanced S -adic languages\nby Léo Poiri
er and Wolfgang Steiner as part of One World Combinatorics on Words Semina
r\n\n\nAbstract\nLéo Poirier and Wolfgang Steiner Factor-balanced \nS\n-a
dic languages\n\nA set of words\, also called a language\, is letter-balan
ced 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 wor
ds of the same length is bounded. The most prominent example of a letter-b
alanced but not factor-balanced language is given by the Thue-Morse sequen
ce. We establish connections between the two notions\, in particular for l
anguages given by substitutions and\, more generally\, by sequences of sub
stitutions. We show that the two notions essentially coincide when the seq
uence of substitutions is proper. For the example of Thue-Morse-Sturmian l
anguages\, we give a full characterisation of factor-balancedness.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/69/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Štěpán Starosta
DTSTART:20230327T130000Z
DTEND:20230327T140000Z
DTSTAMP:20260404T110833Z
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 Semin
ar\n\n\nAbstract\nThe set of morphisms mapping any Sturmian sequence to a
Sturmian sequence forms together with composition the so-called monoid of
Sturm. For this monoid\, we define a faithful representation by $(3\\time
s 3)$-matrices with integer entries. We find three convex cones in $\\math
bb{R}^3$ and show that a matrix $R \\in Sl(\\mathbb{Z}\,3)$ is a matrix r
epresenting a Sturmian morphism if the three cones are invariant under mu
ltiplication by $R$ or $R^{-1}$. This property offers a new tool to study
Sturmian sequences. We provide\nalternative proofs of four known results o
n Sturmian sequences fixed by a primitive morphism and a new result concer
ning the square root of a Sturmian sequence.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/70/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeffrey Shallit
DTSTART:20230403T130000Z
DTEND:20230403T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/71
DESCRIPTION:Title: New Results in Additive Number Theory via Combinatori
cs on Words\nby Jeffrey Shallit as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nAdditive number theory is the study of the ad
ditive properties of integers.\nSurprisingly\, we can use techniques from
combinatorics on words to prove\nresults in this area.\nIn this talk I wil
l discuss the number of representations of an integer N as\na sum of eleme
nts from some famous sets\, such as the evil numbers\, the\nodious\nnumber
s\, the Rudin-Shapiro numbers\, Wythoff sequences\, etc.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/71/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthieu Rosenfeld
DTSTART:20230522T130000Z
DTEND:20230522T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/73
DESCRIPTION:by Matthieu Rosenfeld as part of One World Combinatorics on Wo
rds Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/73/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mélodie Lapointe
DTSTART:20230508T130000Z
DTEND:20230508T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/74
DESCRIPTION:Title: Perfectly clustering words: Induction and morphisms\nby Mélodie Lapointe as part of One World Combinatorics on Words Semin
ar\n\n\nAbstract\nPerfectly clustering words are special factors in trajec
tories of discrete interval exchange transformation with symmetric permuta
tion. If the discrete interval exchange transformation has two intervals\,
they are Christoffel words. Therefore\, perfectly clustering words are a
natural generalization of Christoffel words. In this talk\, an induction o
n discrete interval exchange transformation with symmetric permutation wil
l be presented. This induction sends a discrete interval exchange transfor
mation with symmetric permutation into another one with the same permutati
on but smaller intervals. Moreover\, the induction leads to morphisms\, se
nding a perfectly clustering word to another perfectly clustering word. Fi
nally\, a new bijection between perfectly clustering words and band bricks
over certain gentle algebras will be presented.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/74/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Craig Kaplan
DTSTART:20230515T130000Z
DTEND:20230515T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/75
DESCRIPTION:Title: An aperiodic monotile\nby Craig Kaplan as part of
One World Combinatorics on Words Seminar\n\n\nAbstract\nA set of shapes i
s called aperiodic if the shapes admit tilings of \n the plane\, but none
that have translational symmetry. A longstanding\n open problem asks whet
her a set consisting of a single shape could \n be aperiodic\; such a shap
e is known as an aperiodic monotile or \n sometimes an "einstein". The re
cently discovered "hat" monotile\n settles this problem in two dimensions.
In this talk I provide\n necessary background on aperiodicity and relate
d topics in tiling\n theory\, review the history of the search for for an
aperiodic \n monotile\, and then discuss the hat and its mathematical prop
erties.\n\nFull disclosure: this is the same title and abstract that I jus
t sent to Kevin Hare for the Numeration seminar the week before (May 9th).
I expect that the talks will be largely the same\, but if I have a chanc
e to incorporate any connections to combinatorics on words into my talk fo
r you\, I will.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/75/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bastián Espinoza
DTSTART:20230912T130000Z
DTEND:20230912T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/76
DESCRIPTION:Title: An S -adic characterization of linear-growth complex
ity subshifts\nby Bastián Espinoza as part of One World Combinatorics
on Words Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/76/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Svetlana Puzynina
DTSTART:20231107T140000Z
DTEND:20231107T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/77
DESCRIPTION:Title: Well distributed occurrences property in infinite wor
ds\nby Svetlana Puzynina as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nWe say that an infinite word $u$ on a $d$-ary alphab
et 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 pr
efix of $u$ preceding such occurrence is congruent to $v$ modulo $m$. In t
his talk we will discuss how aperiodic infinite words with well distribute
d occurrences can be used to produce aperiodic pseudorandom number generat
ors with good statistical behavior. We study the well distributed occurren
ces property for certain families of infinite words including words gener
ated by morphisms\, Sturmian words and Arnoux–Rauzy words. The talk is b
ased on new and old results.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/77/
END:VEVENT
BEGIN:VEVENT
SUMMARY:James Currie
DTSTART:20230926T130000Z
DTEND:20230926T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/78
DESCRIPTION:Title: The analogs of overlap-freeness for the period-doubli
ng morphism and for the Fibonacci morphism\nby James Currie as part of
One World Combinatorics on Words Seminar\n\n\nAbstract\nThe Thue-Morse mo
rphism is the binary map $\\mu: 0 \\to 01\, 1 \\to 10$. A word $w$ is\nove
rlap-free if it has no factor of the form $xyxyx$\, where $x$ is\nnon-empt
y. A deep connection between these two concepts is the engine\nbehind seve
ral results:\n\n- The precise characterization of finite prefixes
of infinite\noverlap-free binary words (Fife’s Theorem)\;\n\n- A
precise enumeration of overlap-free binary words\;\n\n- A charact
erization of all binary patterns encountered by the\nThue-Morse word\;\n\n
- The determination of the lexicographically least infinite\noverl
ap-free word.\n\nGiven another morphism\, is there an analog of overlap-fr
eeness which\nfacilitates the proof of similar results? We show that the a
nswer is\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://stable.researchseminars.org/talk/CombinatoricsOnWords/78/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ľubomíra Dvořáková
DTSTART:20231010T130000Z
DTEND:20231010T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/79
DESCRIPTION:Title: String attractors and pseudopalindromic closures\
nby Ľubomíra Dvořáková as part of One World Combinatorics on Words Se
minar\n\n\nAbstract\nIn this contribution we carry on a study of string at
tractors of important classes of sequences. Attractors of minimum size of
factors/prefixes/particular prefixes of the following sequences have been
determined so far: Sturmian sequences (Mantaci\, Restivo\, Romana\, Rosone
\, Sciortino\, 2021\, Dvořáková\, 2022)\, episturmian sequences (Dvoř
áková\, 2022)\, the Tribonacci sequence (Schaeffer and Shallit\, 2021)\,
the Thue-Morse sequence (Kutsukake\, 2020\, Schaeffer and Shallit\, 2021\
, Dolce\, 2023)\, the period-doubling sequence (Schaeffer and Shallit\, 20
21)\, the powers of two sequence (Schaeffer and Shallit\, 2021\, Kociumaka
\, Navarro\, Prezza\, 2021)\, complementary-symmetric Rote sequences (Dvo
řáková and Hendrychová\, 2023). Recently\, string attractors in fixed
points of k-bonacci-like morphisms have been described (Gheeraert\, Romana
\, Stipulanti\, 2023).\n\nIn our talk we aim to present the following resu
lts: Using the fact that standard Sturmian sequences may be obtained when
iterating palindromic closure\, we were able to find attractors of minimum
size of all factors of Sturmian sequences. These attractors were differen
t from the ones found for prefixes by Mantaci et al. It was then straightf
orward to generalize the result to factors of episturmian sequences. Obser
ving usefullness of palindromic closures when dealing with attractors\, we
turned our attention to pseudopalindromic prefixes of the so-called binar
y generalized pseudostandard sequences. We determined the minimum size att
ractors in two cases: for pseudostandard sequences obtained when iterating
uniquely the antipalindromic closure (the minimum size is three) and for
the complementary-symmetric Rote sequences when iterating both palindromic
and antipalindromic closure (the minimum size is two).\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/79/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Herman Goulet-Ouellet
DTSTART:20231024T130000Z
DTEND:20231024T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/80
DESCRIPTION:Title: Density of rational languages under invariant measure
s\nby Herman Goulet-Ouellet as part of One World Combinatorics on Word
s Seminar\n\n\nAbstract\nThe notion of density for languages was studied b
y Schützenberger in the 60s and by Hansel and Perrin in the 80s. In both
cases\, the authors focused on densities defined by Bernoulli measures. In
this talk\, I will present new results about densities of regular languag
es under invariant measures of minimal shift spaces. We introduce a compat
ibility condition which implies convergence of the density to a constant w
hich depends only on the given rational language. This result can be seen
as a form of equidistribution property. The compatibility condition can be
stated either in terms of return words or of a skew product. The passage
between the two forms is made more transparent using simple combinatorial
tools inspired by ergodic theory and cohomology. This is joint work with V
alérie Berthé\, Carl-Fredrik Nyberg Brodda\, Dominique Perrin and Karl P
etersen.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/80/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Seda Albayrak
DTSTART:20231121T140000Z
DTEND:20231121T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/81
DESCRIPTION:Title: Quantitative estimates for the size of an intersectio
n of sparse automatic sets\nby Seda Albayrak as part of One World Comb
inatorics on Words Seminar\n\n\nAbstract\nIn 1979\, Erdős conjectured tha
t for $k \\ge 9$\, $2^k$ is\nnot the sum of distinct powers of $3$. That i
s\, the set of powers of\ntwo (which is $2$-automatic) and the $3$-automat
ic set consisting of\nnumbers whose ternary expansions omit $2$ has finite
intersection. A\ntheorem of Cobham (1969) says that if $k$ and $\\ell$ ar
e two\nmultiplicatively independent natural numbers then a subset of the\n
natural numbers that is both $k$- and $\\ell$-automatic is eventually\nper
iodic. A multidimensional extension of this theorem was later\ngiven by S
emenov (1977). Motivated by Erdős’ conjecture and in\nlight of Cobham
’s theorem\, we give a quantitative version of the\nCobham-Semenov theor
em for sparse automatic sets\, showing that the\nintersection of a sparse
$k$-automatic subset of $\\mathbb{N}^d$ and a\nsparse $\\ell$-automatic su
bset of $\\mathbb{N}^d$ is finite. Moreover\,\nwe give effectively computa
ble upper bounds on the size of the\nintersection in terms of data from th
e automata that accept these\nsets.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/81/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre Béaur
DTSTART:20231219T140000Z
DTEND:20231219T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/82
DESCRIPTION:Title: All I want for Christmas is an algorithm to detect a
Sturmian word in an ω-regular language\nby Pierre Béaur as part of O
ne World Combinatorics on Words Seminar\n\n\nAbstract\nIn the enchanting r
ealm of CoWLand\, where computer science wizards and mathematics enchanter
s gather via the magic of the Internet\, a whimsical elf embarks us on a y
uletide adventure. Our quest? To detect Sturmian words hidden in the snowy
languages of ω-regular automata. As S-adic representations and discrete
lines dance around the Christmas tree\, I will present the mischevious mag
ic of desubstitution and its algorithmic applications. \n\nI start from we
ak ω-automata\, that is\, labeled graphs that accept infinite words\, and
characterize when such automata accept a substitutive word\, a fixed poi
nt\, or a Sturmian word. These methods are effective and provide an algori
thm relying on S-adic representations. On the way\, we find some other nat
ural applications in combinatorics on words and discrete geometry. Then\,
I will explain how the methods translate from weak ω-automata to Büchi a
utomata\, what the limits of our techniques are\, and what are the leads t
o give this fairytale a proper conclusion.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/82/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthieu Rosenfeld
DTSTART:20231205T140000Z
DTEND:20231205T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/83
DESCRIPTION:Title: Word reconstruction using queries on subwords or fact
ors\nby Matthieu Rosenfeld as part of One World Combinatorics on Words
Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/83/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Clemens Müllner
DTSTART:20240109T140000Z
DTEND:20240109T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/84
DESCRIPTION:Title: Synchronizing automatic sequences along Piatetski-Sha
piro sequences\nby Clemens Müllner as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nAutomatic sequences - that is\, sequences
computable by finite automata - have long been studied from the point of
view of combinatorics on words. A notable property of these sequences is t
hat their subword-complexity is at most linear. Avgustinovich\, Fon-Der-Fl
aass and Frid introduced the notion of arithmetic subword-complexity - tha
t is the number of different subwords of length $n$ that appear along some
arithmetic progression.\nThey also showed that a special class of synchro
nizing automatic sequences have at most linear arithmetic subword-complexi
ty and some other class of automatic sequences on the alphabet $\\Sigma$ h
ave maximal possible subword-complexity $|\\Sigma|^n$.\n\nSynchronizing au
tomatic sequences can be efficiently approximated using periodic functions
and are usually more structured than general automatic sequences. We disc
uss a recent result showing that the arithmetic (and even polynomial) subw
ord-complexity of synchronizing automatic sequences grows subexponentially
. This was a key result to show that the subword-complexity of synchronizi
ng automatic sequences along regularly growing sequences (such as Piatetsk
i-Shapiro sequences) grows subexponentially\, which is in stark contrast t
o other automatic sequences such as the Thue-Morse sequence. Moreover\, th
is was a key ingredient to obtain rather precise estimates for the arithme
tic (and polynomial) subword-complexity of general automatic sequences.\n\
nThis is joint work with Jean-Marc Deshouillers\, Michael Drmota\, Andrei
Shubin and Lukas Spiegelhofer.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/84/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jakub Konieczny
DTSTART:20240123T140000Z
DTEND:20240123T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/85
DESCRIPTION:Title: Arithmetical subword complexity of automatic sequence
s\nby Jakub Konieczny as part of One World Combinatorics on Words Semi
nar\n\n\nAbstract\nIt is well-known that the subword complexity of an auto
matic sequence 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 contras
t\, arithmetic subword complexity measures the number of subwords which ap
pear along arithmetic progressions\, and can grow exponentially even for v
ery simple automatic sequences. Indeed\, the classical Thue-Morse sequence
has arithmetic subword complexity $2^{\\ell}$\, which is the maximal poss
ible complexity for $\\{0\,1\\}$-valued sequence.\n\nTogether with Jakub B
yszewski and Clemens Müllner we obtained a decomposition result which all
ows us to express any (complex-valued) automatic sequence as the sum of a
structured part\, which is easy to work with\, and a part which is pseudor
andom or uniform from the point of view of higher order Fourier analysis.
We now apply these techniques to the study of arithmetic subword complexit
y of automatic sequences. We show that for each automatic sequence $a$ the
re exists a parameter $r$ --- which we dub "effective alphabet size" --- s
uch that 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 Byszewski and Clemens Müllner\, and is closely related to the previ
ous talk of Clemens Müllner at One World Combinatorics on Words Seminar.\
n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/85/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Eric Rowland
DTSTART:20240206T140000Z
DTEND:20240206T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/86
DESCRIPTION:Title: Algebraic power series and their automatic complexity
\nby Eric Rowland as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nA theorem of Christol gives a characterization of automatic
sequences over a finite field: a sequence is automatic if and only if its
generating series is algebraic. Since there are two representations for s
uch a sequence -- as an automaton and as a bivariate polynomial -- a natur
al question is how the size of one representation relates to the size of t
he other. Bridy used tools from algebraic geometry to bound the size of th
e minimal automaton in terms of the size of the minimal polynomial. We hav
e a new proof of Bridy's bound that works by converting algebraic sequence
s to diagonals of rational functions. Crucially for our interests\, this a
pproach can be adapted to work not just over a finite field but over the i
ntegers modulo a prime power. This is joint work with Manon Stipulanti and
Reem Yassawi.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/86/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christopher Cabezas
DTSTART:20240220T140000Z
DTEND:20240220T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/87
DESCRIPTION:Title: Large normalizer of odometers and higher-dimensional
automatic sequences\nby Christopher Cabezas as part of One World Combi
natorics on Words Seminar\n\n\nAbstract\nFor a $\\mathbb Z^d$ topological
dynamical system $(X\, T\, \\mathbb Z^d)$\, an isomorphism is a self-homeo
morphism $\\phi : X\\to X$ such that for some matrix $M \\in GL(d\, \\math
bb 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 act
ion of $n \\in \\mathbb Z^d$. The collection of all the isomorphisms forms
a group that is the normalizer of the set of transformations $T^n$. In th
e one-dimensional case isomorphisms correspond to the notion of flip conju
gacy of dynamical systems and by this fact are also called reversing symme
tries.\n\nThese isomorphisms are not well understood even for classical sy
stems. In this talk we will present a description of them for odometers an
d more precisely for $\\mathbb Z^2$-constant base odometers\, that is not
simple. We deduce a complete description of the isomorphism of some $\\mat
hbb Z^2$ minimal substitution subshifts. Thanks to this\, we will give the
first known example of a minimal zero-entropy subshift with the largest p
ossible normalizer group.\nThis is a joint work with Samuel Petite (Univer
sitè de Picardie Jules Verne).\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/87/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Finn Lidbetter
DTSTART:20240305T140000Z
DTEND:20240305T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/88
DESCRIPTION:Title: Improved bound for the Gerver-Ramsey collinearity pro
blem\nby Finn Lidbetter as part of One World Combinatorics on Words Se
minar\n\n\nAbstract\nAbstract: Let $S$ be a finite subset of $\\mathbb{Z}^
n$. A vector\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 n
o\n$5^{11}+1=48\,828\,126$ points are collinear. Using the same general\na
pproach\, but with the aid of a computer search\, we show how to\nimprove
the bound to $189$. We begin by restating the infinite\n$S$-walk as the fi
xed point of iterating a morphism defined for a $12$\nletter alphabet.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/88/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Radoslaw Piórkowski
DTSTART:20240416T130000Z
DTEND:20240416T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/89
DESCRIPTION:Title: Universal quantification in automatic structures —
an ExpSpace-hard nut to crack\nby Radoslaw Piórkowski as part of One
World Combinatorics on Words Seminar\n\n\nAbstract\nAutomatic structures a
re structures whose universe and relations can be represented as regular l
anguages. It follows from the standard closure properties of regular langu
ages that the first-order theory of an automatic structure is decidable. \
n\nWhile existential quantifiers can be eliminated in linear time by appli
cation of a homomorphism\, universal quantifiers are commonly eliminated v
ia the identity ∀x. Φ ≡ ¬(∃x. ¬Φ). If Φ is represented in the s
tandard way as an NFA\, a priori this approach results in a doubly exponen
tial blow-up. However\, the recent literature has shown that there are cla
sses of automatic structures for which universal quantifiers can be elimin
ated without this blow-up when treated as first-class citizens and not res
orting to double complementation. The existing lower bounds for some class
es of automatic structures show that a singly exponential blow-up is unavo
idable when eliminating a universal quantifier\, but it is not known wheth
er there may be better approaches that avoid the naïve doubly exponential
blow-up. \nWe answer this question negatively.\n\nIn my talk\, following
a short introduction to the field of automatic structures\, I will present
the construction of a family of NFA representing automatic relations for
which the minimal NFA recognising the language after a universal projectio
n step is doubly exponential\, and deciding whether this language is empty
is ExpSpace-complete.\n\n\nBased on the paper: https://drops.dagstuhl.de/
entities/document/10.4230/LIPIcs.CONCUR.2023.13 \n\nAuthors: Christoph Haa
se\, R.P.\n\nKeywords: automatic structures\, universal projection\, tilin
g problems\, state complexity.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/89/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cor Kraaikamp
DTSTART:20240319T140000Z
DTEND:20240319T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/90
DESCRIPTION:Title: An introduction to $N$ -expansions with a finite set
of digits\nby Cor Kraaikamp as part of One World Combinatorics on Wor
ds Seminar\n\n\nAbstract\nIn this talk $N$-expansions\, and in particular
$N$-expansions with a finite set\nof digits\, will be introduced. Although
$N$-expansions were introduced as\nrecent as 2008 by Ed Burger and some o
f his students\, quite a number of\npapers have appeared on these variatio
ns of the regular continued fraction\nexpansion. By choosing a domain for
the underlying Gauss-map which does\nnot contain the origin\, a continued
fraction with finitely many digits was\nintroduced by Niels Langeveld in h
is MSc-thesis. It turns out that these\ncontinued fraction algorithms exhi
bit a very complicated and surprising rich\ndynamical behavior.\n\nThis ta
lk is based on joint work with Yufei Chen (Shanghai\, Delft)\, Jaap\nde Jo
nge (UvA\, Amsterdam)\, Karma Dajani (Utrecht)\, Niels Langeveld\n(Montan
U.\, Leoben)\, Hitoshi Nakada (Keio\, Yokohama)\, and Niels van der\nWekke
n (Netcompany).\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/90/
END:VEVENT
BEGIN:VEVENT
SUMMARY:John Campbell
DTSTART:20240402T130000Z
DTEND:20240402T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/91
DESCRIPTION:Title: On the evaluation of infinite products involving auto
matic sequences\nby John Campbell as part of One World Combinatorics o
n Words Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/91/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michael Baake
DTSTART:20240430T130000Z
DTEND:20240430T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/92
DESCRIPTION:Title: Hats\, CAPs and Spectres\nby Michael Baake as par
t of One World Combinatorics on Words Seminar\n\n\nAbstract\nThe recently
discovered Hat is an aperiodic\nmonotile for the Euclidean plane\, which n
eeds a reflected\nversion for this property. The Spectre does not have thi
s\n(tiny) deficiency. We discuss the topological and dynamical\nproperties
of the Hat tiling\, how the CAP relates to it\, and\nwhat the long-range
order of both tilings is. Finally\, we\nbriefly describe the analogous str
ucture for the Spectre tiling.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/92/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Josef Rukavicka
DTSTART:20240514T130000Z
DTEND:20240514T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/93
DESCRIPTION:Title: Restivo Salemi property for $\\alpha$-power free lang
uages with $\\alpha \\geq 5$ and $k \\geq 3$ letters\nby Josef Rukavic
ka as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn 2
009\, Shur published the following conjecture: Let $L$ be a power-free lan
guage and let $e(L)\\subseteq L$ be the set of words of $L$ that can be ex
tended 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}$ d
enote an $\\alpha$-power free language over an alphabet with $k$ letters\,
where $\\alpha$ is a positive rational number and $k$ is positive integer
. We prove the conjecture for the languages $L_{k\,\\alpha}$\, where $\\al
pha\\geq 5$ and $k \\geq 3$.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/93/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pascal Ochem
DTSTART:20240528T130000Z
DTEND:20240528T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/94
DESCRIPTION:Title: Characterization of morphic words\nby Pascal Oche
m as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nThe f
amous Hall-Thue word\, fixed point of the morphism\n0 -> 012\, 1 -> 02\, 2
-> 1\, is essentially the only infinite\nternary word avoiding squares an
d the words 010 and 212.\n\nI will present many examples of this phenomeno
n\, that is\,\nwhen every recurrent word satisfying some avoidance constra
ints\nhas the same factor set as a morphic word.\n\nThis is a joint work w
ith Golnaz Badkobeh\, Matthieu Rosenfeld\,\nL'ubomíra Dvořáková\, Dani
ela Opočenská\, Aseem Baranwal\,\nJames Currie\, Lucas Mol\, Narad Rampe
rsad\, and Jeffrey Shallit.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/94/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Markus Whiteland
DTSTART:20240611T130000Z
DTEND:20240611T140000Z
DTSTAMP:20260404T110833Z
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\n
Abstract\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 Allouche et al. [Comb. Theory 1\, 2021] (in passing) and Cassaigne et
al. [Int. J. Found. Comput. 22\, 2011]\; the latter characterises Parikh-c
ollinear morphisms as those morphisms that map any infinite word (over the
domain alphabet) to a word with bounded abelian complexity.\n\nIn this ta
lk I will focus on properties of Parikh-collinear morphisms and their fixe
d points from the viewpoint of binomial complexities. We will also conside
r automatic (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. Stip
ulanti.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/95/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julien Cassaigne
DTSTART:20240625T130000Z
DTEND:20240625T140000Z
DTSTAMP:20260404T110833Z
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 o
f infinite words (or of subshifts) have a subword complexity\nfunction $p(
n)$ that grows linearly. It has sometimes a very simple form\n(such as $n
+ 1$\, $2n + 1$\, etc.)\, but often a more complicated behaviour\,\nas fo
r the Thue-Morse word. In his Ph.D. thesis\, Alex Heinis introduced the\n
set $\\Omega$ of pairs $(\\alpha\,\\beta)$ such that $\\alpha = \\liminf p
(n)/n$\nand $\\beta = \\limsup p(n)/n$ for some infinite word. For instan
ce\, the\nThue-Morse word gives the point $(3\, 10/3)$. But not every poi
nt with\n$\\alpha \\leq \\beta$ can be obtained\, and it is a challenge to
characterize\npoints in $\\Omega$. We present some properties of this se
t\, and some\nquestions that we find interesting.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/96/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jamie Simpson
DTSTART:20240709T130000Z
DTEND:20240709T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/97
DESCRIPTION:Title: Palindromic Periodicities\nby Jamie Simpson as pa
rt of One 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 length at least $|ps|$ is called a palindromic periodicity. In this
talk I will first describe some simple properties of these objects and the
n show how they can appear. For example a word which is both periodic and
a palindrome is a palindromic periodicity. Next I'll present a periodicit
y lemma similar to the Fine Wilf Lemma but applied to palindromic periodic
ities. The talk will finish with some suggestions for further research.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/97/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jia-Yan Yao
DTSTART:20240910T130000Z
DTEND:20240910T140000Z
DTSTAMP:20260404T110833Z
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 this talk we introduce a new notion to measure the complexity of autom
atic numbers\, which are either rational or transcendental. We study basic
properties of this notion\, and exhibit an algorithm to compute it. In pa
rticular\, we shall characterize all the automatic numbers which are trans
parent. As applications\, we shall also compute the complexity of some wel
l-known automatic numbers.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/98/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Elżbieta Krawczyk
DTSTART:20241203T140000Z
DTEND:20241203T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/99
DESCRIPTION:Title: Quasi-fixed points of substitutions and substitutive
systems\nby Elżbieta Krawczyk as part of One World Combinatorics on W
ords Seminar\n\n\nAbstract\nWe study automatic sequences and automatic sys
tems (symbolic dynamical systems) generated by general constant length (no
nprimitive) substitutions. While an automatic system is typically uncounta
ble\, the set of automatic sequences is countable\, implying that most seq
uences within an automatic system are not themselves automatic. We provide
a complete classification of automatic sequences that lie in a given auto
matic system in terms of the so-called quasi-fixed points of the substitut
ion defining the system. Quasi-fixed points have already appeared implicit
ly in a few places (e.g. in the study of substitutivity of lexicographica
lly minimal points in substitutive systems or in the study of subsystems o
f substitutive systems) and they have been described in detail by Shallit
and Wang and\, more recently\, B\\'eal\, Perrin\, and Restivo . We conject
ure that a similar statement holds for general nonconstant length substitu
tions.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/99/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yuto Nakashima
DTSTART:20241217T140000Z
DTEND:20241217T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/100
DESCRIPTION:Title: On the Number of Non-equivalent Parameterized Square
s 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 squar
e when $s = xy$ for strings $x$\, $y$ and $x$ and $y$ are parameterized eq
uivalent.\nKociumaka et al. showed the number of parameterized squares\, w
hich are non-equivalent in parameterized equivalence\, in a string of leng
th $n$ that contains $\\sigma$ distinct characters is at most $2 \\sigma!
n$ [TCS 2016].\nRecently\, we showed that the maximum number of non-equiva
lent parameterized squares is less than $\\sigma n$\, which significantly
improves the best-known upper bound by Kociumaka et al.\n\nThis is a joint
work with Rikuya Hamai\, Kazushi Taketsugu\, Shunsuke Inenaga\, and Hideo
Bannai (presented at SPIRE 2024).\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/100
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luke Schaeffer
DTSTART:20240924T130000Z
DTEND:20240924T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/101
DESCRIPTION:Title: Summation and transduction of automatic sequences\nby Luke Schaeffer as part of One World Combinatorics on Words Seminar\n
\n\nAbstract\nWe examine the theory of computing partial sums or transduct
ions in automatic sequences\, including a theorem of Dekking and its gener
alization. We give a number of examples involving paperfolding words and S
turmian sequences.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/101
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mehdi Golafshan
DTSTART:20241008T130000Z
DTEND:20241008T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/102
DESCRIPTION:Title: Factor complexity of the most significant digits and
unipotent dynamics on a torus\nby Mehdi Golafshan as part of One Worl
d Combinatorics on Words Seminar\n\n\nAbstract\nIn this talk\, we explore
the dynamics of unipotent flows on a torus and how these techniques lead t
o interesting applications in number theory. Specifically\, I'll focus on
the following problem: let \\(d\\) be a positive integer\, and \\(a > 0\\)
be a real number. Consider a square-free integer \\(b \\geqslant 5\\) suc
h that \\(a\\) and \\(b\\) are multiplicatively independent. We then exami
ne the sequence \\((\\mathbf{w}_n)\\)\, where \\(\\mathbf{w}_n\\) represen
ts the most significant digit of \\(a^{n^d}\\) when written in base \\(b\\
). I will present our result\, showing that the complexity function of thi
s sequence\, with only a finite number of exceptions\, is a polynomial fun
ction. This work connects dynamics on homogeneous spaces with problems in
symbolic dynamics and number theory\, offering new insights into sequence
complexity.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/102
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Olivier Carton
DTSTART:20241022T130000Z
DTEND:20241022T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/103
DESCRIPTION:Title: Mahler equations for Zeckendorf numeration\nby
Olivier Carton as part of One World Combinatorics on Words Seminar\n\n\nAb
stract\nLet $U = (u_n)$ be a Pisot numeration system. A sequence $(f_n)$
taking values\nover a commutative ring $R$\, possibly infinite\, is said t
o be //$U$-regular//\nif there exists a //weighted// automaton which outpu
ts $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$-regul
ar sequences\, and //$q$-Mahler type//\nequations. In particular a $q$-reg
ular sequence gives a solution to an\nequation of $q$-Mahler type\, and co
nversely\, the solution of an\n//isolating//\, or Becker\, equation of $q$
-Mahler type is $q$-regular.\n\nWe define generalised equations of $Z$-Mah
ler type\, based on the Zeckendorf\nnumeration system $Z$. We show that if
a sequence over a commutative ring is\n$Z$-regular\, then it is the seque
nce of coefficients of a series which is a\nsolution of a $Z$-Mahler equat
ion. Conversely\, if the $Z$-Mahler equation is\nisolating\, then its solu
tions define $Z$-regular sequences. We provide an\nexample to show that t
here exist non-isolating $Z$-Mahler equations whose\nsolutions do not defi
ne $Z$-regular sequences. Our proof yields a new\nconstruction of weighted
automata that generate classical $q$-regular\nsequences.\n\nThis is joint
work with Reem Yassawi.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/103
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benjamin Hellouin de Menibus
DTSTART:20241105T140000Z
DTEND:20241105T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/104
DESCRIPTION:Title: String attractors for infinite words\nby Benjami
n Hellouin de Menibus as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nA string attractor of a word w is a set of marked positions
such that every factor of w has an occurrence that crosses one of the mar
ked positions. This is a recent concept whose motivation comes from the st
udy of compression algorithms\, but that was studied very soon after for i
ts combinatorial properties. In particular\, the size or span of the small
est string 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 f
amilies of classical words\, such as the prefixes of the Fibonacci word.\n
\nWhile it is fruitful to study smallest string attractors on finite prefi
xes or factors of infinite words\, we can also define string attractors di
rectly on infinite words. Unfortunately\, there is no good notion of small
est string attractor in this setting\, except when there is a finite one\,
which in the one-sided case means that the word is periodic.\n\nFortunate
ly\, the two-sided case is more rich in this regard\, and is the topic of
this talk. We study and completely characterise two-sided infinite words t
hat admit a finite string attractor\, and relate the size of the smallest
attractor to their complexity function. We also get another characterisati
on of (quasi-)Sturmian words. I will also mention some side results regard
ing periodic string attractors and / or string attractors for shifts.\n\nT
his is a joint work with Pierre Béaur and France Gheeraert.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/104
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Léo Vivion
DTSTART:20241119T140000Z
DTEND:20241119T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/105
DESCRIPTION:Title: Balancedness constants of words generated by billiar
ds in the hypercube\nby Léo Vivion as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nA hypercubic billiard word in dimension $
d$ is an infinite $d$-ary word encoding the faces successively hit by a bi
lliard ball moving in the unit cub of $\\mathbb{R}^d$\, in which two paral
lel faces are labeled by the same letter. Square billiard words generated
by a (billiard ball with an initial) momentum with rationally independent
coordinates are Sturmian\, so hypercubic billiard words generated by a mom
entum with rationally independent coordinates are one dynamical generaliza
tion of Sturmian words. Hence\, it is natural to ask which properties sati
sfied by Sturmian words are still satisfied by hypercubic billiard words.\
n\nWhile the subword complexity of hypercubic billiard words has been exte
nsively studied at the end of the 1990s and the beginning of the 2000s (Ar
noux\, Mauduit\, Shiokawa and Tamura 1994\, Baryshnikov 1995 and Bédaride
2003-2009)\, their abelian properties have been much less studied: only V
uillon (2003) initiated the study of their balancedness.\n\nIn this talk\,
I will first recall the results obtained by Vuillon\, and then\, give a c
omplete characterization of the imbalance of hypercubic billiard words gen
erated by a momentum with rationally independent coordinates. In a second
part\, I will also discuss the case of momenta with rationally dependent c
oordinates.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/105
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christophe Reutenauer
DTSTART:20250114T140000Z
DTEND:20250114T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/106
DESCRIPTION:Title: Christoffel matrices and Sturmian determinants\n
by Christophe Reutenauer as part of One World Combinatorics on Words Semin
ar\n\n\nAbstract\nWork in collaboration with Jeffrey Shallit.\n\n1. The se
t of Christoffel matrices (that is\, Burrows-Wheeler matrices of Christoff
el words) 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 independ
ently by Luca Zamboni)\n\n2. The determinant of a Christoffel matrix has a
simple form\, using the Zolotareff symbol (the latter extends the Jacobi
symbol).\n\n3. Taking $n$ factors of length $n$ of a Sturmian sequence ove
r $0$\, $1$\, one obtains a matrix and a determinant. There are$n+1$ such
determinants\; ordering them suitably\, these $n+1$ determinants form a w
ord on a two- or three-letter alphabet contained in $Z$\; this word is per
fectly clustering. If there are three letters\, then one of them is the su
m of the two others.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/106
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lucas Mol
DTSTART:20250128T140000Z
DTEND:20250128T150000Z
DTSTAMP:20260404T110833Z
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\n
Abstract\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 sum 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\, Ram
persad\, and Shallit.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/107
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Josef Rukavicka
DTSTART:20250211T140000Z
DTEND:20250211T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/108
DESCRIPTION:Title: Palindromic length of infinite aperiodic words\n
by Josef Rukavicka as part of One World Combinatorics on Words Seminar\n\n
\nAbstract\nThe palindromic length of the finite word $v$ is equal to the
minimal number of palindromes whose concatenation is equal to $v$. It was
conjectured in 2013 that for every infinite aperiodic word $x$\, the palin
dromic length of its factors is not bounded.\nWe prove this conjecture to
be true.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/108
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bartek Pawlik
DTSTART:20250225T140000Z
DTEND:20250225T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/109
DESCRIPTION:Title: Words Avoiding Tangrams\nby Bartek Pawlik as par
t of One World Combinatorics on Words Seminar\n\n\nAbstract\nWork in colla
boration with Michał Dębski\, Jarosław Grytczuk\, Jakub Przybyło and M
ałgorzata Śleszyńska-Nowak.\n\nIf\, in a given word $W$\, each letter a
ppears an even number of times\, then $W$ can be split into two identical\
, disjoint subwords. For example\, the word $\\mathtt{hotshots}$ can be sp
lit into two $\\mathtt{hots}$ by dividing the word exactly in the middle:
$\\mathtt{hots\\\,|\\\,hots}$. More generally\, any square can be separate
d into two identical words with a single cut. The word $\\mathtt{tattletal
e}$ requires three cuts: $\\mathtt{tat\\\,|\\\,tle\\\,|\\\,ta\\\,|\\\,le}$
to split it into two words $\\mathtt{tatle}$. The minimal number of cuts
needed to divide a word $W$ into two identical subwords is called the {\\i
t cut number} of $W$. During the lecture\, I will discuss several topics r
elated to the cut number.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/109
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre Letouzey
DTSTART:20250311T140000Z
DTEND:20250311T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/110
DESCRIPTION:Title: Generalizing some Hofstadter functions: G\, H and be
yond\nby Pierre Letouzey as part of One World Combinatorics on Words S
eminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/110
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vuong Bui
DTSTART:20250325T140000Z
DTEND:20250325T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/111
DESCRIPTION:Title: An explicit condition for boundedly supermultiplicat
ive subshifts\nby Vuong Bui as part of One World Combinatorics on Word
s Seminar\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 supermultiplica
tive. That is\, there exist constants $C>0$ and $\\alpha\\ge 0$\, such th
at for all $n$\, the number of words of length $n$ in $L(A\,F)$ is between
$\\alpha^n$ and $C\\alpha^n$. In some settings\, our condition provides a
way to compute $C$\, which implies that $\\alpha$\, the growth rate of th
e language\, is also computable whenever our condition holds.\nWe also app
ly our technique to the specific setting of power-free words where the arg
ument can be slightly refined to provide better bounds. Finally\, we apply
a similar idea to $F$-free circular words and in particular we make progr
ess toward a conjecture of Shur about the number of square-free circular w
ords.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/111
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hajime Kaneko
DTSTART:20250408T130000Z
DTEND:20250408T140000Z
DTSTAMP:20260404T110833Z
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 Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/112
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Be'eri Greenfeld
DTSTART:20250422T130000Z
DTEND:20250422T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/113
DESCRIPTION:Title: On the Complexity of Infinite Words\nby Be'eri G
reenfeld 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 ope
n problem in the combinatorics of infinite words is the {\\it inverse prob
lem}: describe which functions $f: \\mathbb N \\to \\mathbb N$ arise as co
mplexity functions of infinite words. Such functions must be non-decreasin
g and\, unless eventually constant\, strictly increasing\; they must also
be submultiplicative\, i.e.\, $f(n+m)≤f(n)f(m)$. Many interesting result
s\, both positive and negative\, have been obtained in this direction.\n\n
We resolve this problem up to asymptotic equivalence in the sense of large
-scale geometry. Specifically\, given any increasing\, submultiplicative f
unction $f$\, we construct an infinite recurrent word $w$ such that $c f(c
n) ≤ p_w(n) ≤ d f(dn)$ for some constants $c\,d>0$. For uniformly recu
rrent words\, we obtain a weaker version allowing a linear error factor. T
ime permitting\, we will discuss connections and applications of these res
ults to asymptotic questions in algebra.\n\nJoint work with C. G. Moreira
and E. Zelmanov.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/113
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jarkko Peltomäki
DTSTART:20250506T130000Z
DTEND:20250506T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/114
DESCRIPTION:Title: The repetition threshold for ternary rich words\
nby Jarkko Peltomäki as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nIn the recent years\, it has been popular to determine the
least critical exponent in specific families of infinite words. In this ta
lk\, I will explain what is known about the least critical exponents for i
nfinite words that are rich in palindromes. In particular\, I will outline
the proof of our result that the least critical exponent for ternary rich
infinite words equals $1 + 1/(3 - \\mu) \\approx 2.25876324$\, where $\\m
u$ is the unique real root of the polynomial $x^3 - 2x^2 - 1$. This result
is based on proving a structure theorem for ternary rich infinite words t
hat avoid $16/7$-powers. In addition\, I discuss some recent progress on d
etermining the least asymptotic critical exponents for rich infinite words
.\n\nJoint work with L. Mol and J. D. Currie.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/114
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pranjal Jain
DTSTART:20250520T130000Z
DTEND:20250520T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/115
DESCRIPTION:Title: Partial Sums of Binary Subword-Counting Sequences\nby Pranjal Jain as part of One World Combinatorics on Words Seminar\n\n
\nAbstract\nLet $w$ be a finite word over the alphabet $\\{0\,1\\}$. For a
ny natural number $n$\, let $s_w(n)$ denote the number of occurrences of $
w$ in the binary expansion of $n$ as a scattered subsequence. The talk aim
s to provide a systematic way of studying the growth of the partial sum $\
\sum_{n=0}^N (-1)^{s_w(n)}$ as $N \\to \\infty$. In particular\, these tec
hniques 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 t
he ideas using the case of $w=01\,011$. The talk is based on joint work wi
th Shuo Li.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/115
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Curtis Bright
DTSTART:20250603T130000Z
DTEND:20250603T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/116
DESCRIPTION:Title: Mathematical Problems with SATisfying Solutions\
nby Curtis Bright as part of One World Combinatorics on Words Seminar\n\n\
nAbstract\nAutomated reasoning tools have been effectively used to solve a
variety of problems in discrete mathematics. In this talk\, I will intro
duce satisfiability (SAT) solvers and highlight a variety of problems in d
iscrete mathematics that have been tackled with a SAT solver. As a case s
tudy\, I will demonstrate how a SAT solver can be used to make progress on
a question arising in combinatorics on words involving North-East lattice
paths.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/116
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noy Soffer Aranov
DTSTART:20250617T130000Z
DTEND:20250617T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/117
DESCRIPTION:Title: Escape of Mass of Sequences\nby Noy Soffer Arano
v as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nOne w
ay to study the distribution of nested quadratic number fields satisfying
fixed arithmetic relationships is through the evolution of continued fract
ion expansions. In the function field setting\, it was shown by de Mathan
and Teullie that given a quadratic irrational $\\Theta$\, the degrees of t
he periodic part of the continued fraction of $t^n\\Theta$ are unbounded.
Paulin and Shapira improved this by proving that quadratic irrationals exh
ibit partial escape of mass. Moreover\, they conjectured that they must ex
hibit full escape of mass. We construct counterexamples to their conjectur
e in every characteristic. In this talk we shall discuss the technique of
proof as well as the connection between escape of mass in continued fracti
ons\, Hecke trees\, and number walls. This is part of joint works with Ere
z Nesharim and Uri Shapira and with Steven Robertson.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/117
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Elżbieta Krawczyk
DTSTART:20250715T130000Z
DTEND:20250715T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/118
DESCRIPTION:Title: Quasi-fixed points of substitutions and substitutive
systems\nby Elżbieta Krawczyk as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nWe study automatic sequences and automatic sy
stems (symbolic dynamical systems) generated by general constant length (n
onprimitive) substitutions. While an automatic system is typically uncount
able\, the set of automatic sequences is countable\, implying that most se
quences within an automatic system are not themselves automatic. We provid
e a complete classification of automatic sequences that lie in a given aut
omatic system in terms of the so-called quasi-fixed points of the substitu
tion defining the system. Quasi-fixed points have already appeared implici
tly in a few places (e.g. in the study of substitutivity of lexicographica
lly minimal points in substitutive systems or in the study of subsystems o
f substitutive systems) and they have been described in detail by Shallit
and Wang and\, more recently\, Béal\, Perrin\, and Restivo . We conjectur
e that a similar statement holds for general nonconstant length substituti
ons.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/118
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gandhar Joshi
DTSTART:20250902T130000Z
DTEND:20250902T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/119
DESCRIPTION:Title: Monochromatic Arithmetic Progressions in Sturmian se
quences\nby Gandhar Joshi as part of One World Combinatorics on Words
Seminar\n\n\nAbstract\nThis is joint work with Dan Rust. We define Monochr
omatic arithmetic progression (MAP) as the repetition of a symbol (traditi
onally colour) with a constant difference in a sequence. We study threshol
ds of the lengths of MAPs in the Fibonacci word in our paper https://doi.o
rg/10.1016/j.tcs.2025.115391\, which not only resolves a few problems left
open by previous works revolving around MAPs in symbolic sequences but al
so reveals a straightforward method to find a formula that finds longest l
engths of MAPs for all Sturmians. This extension is dealt with in the auth
or's PhD thesis.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/119
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kaisei Kishi
DTSTART:20250916T130000Z
DTEND:20250916T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/120
DESCRIPTION:Title: Net Occurrences in Fibonacci and Thue-Morse Words\nby Kaisei Kishi as part of One World Combinatorics on Words Seminar\n\n
\nAbstract\nIn a string $T$\, an occurrence of a substring $S=T[i ... j]$
is a net occurrence if $S$ is repeated in $T$\, while both left extension
$T[i-1\, ... j]$ and right extension $T[i\, ... j+1]$ are unique in $T$. T
he number of net occurrences of $S$ in $T$ is called its net frequency. Co
mpared with ordinary frequency\, net frequency highlights the more signifi
cant occurrences of $S$ in $T$. In this talk\, I will present several prop
erties of net occurrences and describe techniques to identify all the net
occurrences in Fibonacci and Thue-Morse words. In particular\, I will expl
ain the technique to characterize the occurrences of smaller-order Fibonac
ci and Thue-Morse words. This is a joint work with Peaker Guo.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/120
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Idrissa Kaboré
DTSTART:20251028T140000Z
DTEND:20251028T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/121
DESCRIPTION:Title: POSTPONED\nby Idrissa Kaboré as part of One Wor
ld Combinatorics on Words Seminar\n\n\nAbstract\nIn this talk\, first\, I
will recall the notions of modulo-recurrent words and of window complexity
. These notions are introduced in 2007. Then\, I present some properties o
f these notions. After that\, I will present the notions of uniform modulo
-recurrence and of strong modulo-recurrence. These notions are defined rec
ently in a joint work with Julien Cassaigne. Sturmian words are uniformly
(resp. strongly) modulo-recurrent words. Then\, I will address the window
complexity of the Thue-Morse. To finish\, I will present a recurrent aperi
odic word with bounded window complexity.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/121
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aleksi Vanhatalo
DTSTART:20251111T140000Z
DTEND:20251111T150000Z
DTSTAMP:20260404T110833Z
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\
nAbstract\nA very common problem type in combinatorics on words is to cons
truct words (under constraints) that avoid repetition. This is often done
by constructing suitable morphisms. Here we flip the setup: we ask how goo
d morphisms are at introducing repetitions into words. Periodic morphisms
are trivially very good at this\, but how about less trivial classes of mo
rphisms?\n\nWe consider a few variations of this question. We characterize
finite words that do not have an upper bound on fractional or integer exp
onents when mapped via injective morphisms. Then we consider the asymptoti
c critical exponent of infinite words. While we consider all finite alphab
et sizes\, these variations are better understood in the binary case. This
talk is an extended version of the one presented at DLT 2025. It is based
on joint work with Eva Foster and Aleksi Saarela\, and on ongoing researc
h.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/122
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ignacio Mollo
DTSTART:20251125T140000Z
DTEND:20251125T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/123
DESCRIPTION:Title: Is fully shuffling a rational operation?\nby Ign
acio Mollo as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nA shuffler is a 3-tape transducer specialized in the shuffling of word
s. These automata define rational sets in the so-called shuffling monoid\,
which map directly to regular shuffle languages. In this talk we look at
rational relations of words and wonder whether their full shuffle is ratio
nal: we conclude that it's very rare that the full shuffle of a rational r
elation remains rational but find very interesting examples where rational
ity can be assured.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/123
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Antoine Julien
DTSTART:20251014T130000Z
DTEND:20251014T140000Z
DTSTAMP:20260404T110833Z
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\nAbstract\nThis presentation is concerned with hypercubic billiards wi
th irrational trajectories. In this talk\, I will present the relationship
between balance properties in hypercubic billiards\, and subshift cohomol
ogy. \n\nMore precisely\, I will define cohomology for subshifts and (time
permitting) illustrate with examples of how cohomology has previously bee
n used in symbolic dynamics. Then\, I will present the link between cohomo
logy and balance for billiard sequences. Finally\, I will explain how resu
lts of Kellendonk and Sadun on the dimension of some cohomology spaces imp
lies that billiard words in cubes of dimension at least 3 cannot be balanc
ed on all factors.\n\nIn the case of billiards in the cube\, we also showe
d (using other methods) that these sequences are not balanced on factors o
f length 2.\n\nJoint work with Nicolas Bédaride and Valérie Berthé.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/124
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Florin Manea
DTSTART:20251209T140000Z
DTEND:20251209T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/125
DESCRIPTION:Title: Linear Time Subsequence and Supersequence Regex Matc
hing\nby Florin Manea as part of One World Combinatorics on Words Semi
nar\n\n\nAbstract\nIt is well-known that checking whether a given string $
w$ matches a given regular expression $r$ can be done in quadratic time $O
(|w|⋅ |r|)$ and that this cannot be improved to a truly subquadratic run
ning time of $O((|w|⋅ |r|)^{1-\\varepsilon})$ assuming the strong expone
ntial time hypothesis (SETH). We study a different matching paradigm where
we ask instead whether $w$ has a subsequence that matches $r$\, and show
that regex matching in this sense can be solved in linear time $O(|w| + |r
|)$. Further\, the same holds if we ask for a supersequence. We show that
the quantitative variants where we want to compute a longest or shortest s
ubsequence 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 natura
l string relations like the infix\, prefix\, left-extension or extension r
elation instead of the subsequence and supersequence relation. We further
study the complexity of the universal problem where we ask if all subseque
nces (or supersequences\, infixes\, prefixes\, left-extensions or extensio
ns) of an input string satisfy a given regular expression.\n\nThis is base
d on the paper: Antoine Amarilli\, Florin Manea\, Tina Ringleb\, Markus L.
Schmid: Linear Time Subsequence and Supersequence Regex Matching. MFCS 20
25: 9:1-9:19\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/125
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Louis Marin
DTSTART:20260106T140000Z
DTEND:20260106T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/127
DESCRIPTION:Title: Maximal 2-dimensional binary words of bounded degree
\nby Louis Marin as part of One World Combinatorics on Words Seminar\n
\n\nAbstract\n(Authors: Alexandre Blondin Massé\, Alain Goupil\, Raphael
L'Heureux\, Louis Marin)\n\nLet $d$ be an integer between $0$ and $4$\, an
d $W$ be a $2$-dimensional word of dimensions $h \\times w$ on the binary
alphabet $\\{0\, 1\\}$\, where $h\, w \\in \\mathbb Z > 0$. Assume that ea
ch occurrence of the letter $1$ in $W$ is adjacent to at most $d$ letters
$1$. We provide an exact formula for the maximum number of letters $1$ tha
t can occur in $W$ for fixed $(h\, w)$. As a byproduct\, we deduce an uppe
r bound on the length of maximum snake polyominoes contained in a $h \\tim
es w$ rectangle.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/127
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Savinien Kreczman
DTSTART:20260120T140000Z
DTEND:20260120T150000Z
DTSTAMP:20260404T110833Z
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 Combina
torics on Words Seminar\n\n\nAbstract\nThe Thue-Morse\, Fibonacci-Thue-Mor
se and Allouche-Johnson words are related to the binary\, Zeckendorf and N
arayana numeration systems respectively\, as they count the parity of the
number of ones in representations of natural numbers in those systems. The
se three numeration systems can be seen as the special cases for k=1\,2\,3
of a positional 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
elements 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 family\, the first concerning the first difference of their factor co
mplexity and the second concerning their asymptotic critical exponent. In
this talk\, we will prove both conjectures by studying bispecial factors w
ithin those words. We will highlight a method by K.Klouda allowing us to f
ully list those bispecial factors and show how this list allows us to atta
ck the conjectures in question.\nJoint work with L'ubomíra Dvořáková a
nd Edita Pelantová.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/128
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Annika Huch
DTSTART:20260203T140000Z
DTEND:20260203T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/129
DESCRIPTION:Title: A Word Reconstruction Problem for Polynomial Regular
Languages\nby Annika Huch as part of One World Combinatorics on Words
Seminar\n\n\nAbstract\nThe reconstruction problem concerns the ability to
uniquely determine an unknown word from querying information on the numbe
r of occurrences of chosen subwords. In the joined work with M. Golafshan
and M. Rigo we focused on the reconstruction problem when the unknown word
belongs to a known polynomial regular language\, i.e.\, \nits growth func
tion is bounded by a polynomial. Exploiting the combinatorial and structur
al properties of these languages\, we are able to translate queries into p
olynomial equations and transfer the problem of unique reconstruction to f
inding those sets of queries such that their polynomial equations have a u
nique integer solution.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/129
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Steven Robertson
DTSTART:20260217T140000Z
DTEND:20260217T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/130
DESCRIPTION:Title: Number walls of automatic sequences\nby Steven R
obertson as part of One World Combinatorics on Words Seminar\n\n\nAbstract
\nGiven any one-dimensional sequence S\, one can generate a unique two-dim
ensional sequence by considering the determinants of the Toeplitz matrices
defined by S. This is known as the number wall of S. It is conjectured th
at if S is automatic\, then the number wall of S is itself a two-dimension
al automatic sequence. In this talk\, we will discuss evidence towards thi
s conjecture as well as some recent partial results. The talk aims to be a
ccessible for people with no experience of number walls.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/130
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ingrid Vukusic
DTSTART:20260303T140000Z
DTEND:20260303T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/131
DESCRIPTION:Title: Balanced rectangles over Sturmian words\nby Ingr
id Vukusic as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nOne of the many properties of the famous infinite Fibonacci word $0100
1010\\cdots$ is that it is \\textit{balanced}. This means that any two blo
cks of the same length have either the same weight or their weights are of
f by $1$. Results by Berth\\'e and Tijdeman show that a 2-dimensional vari
ant of the Fibonacci word cannot be balanced. However\, for certain pairs
$(m\,n)$\, the $m\\times n$ rectangles are balanced\, and recently all suc
h $(m\,n)$ were fully characterised. We extend this characterisation to co
mpletely general Sturmian words. The proof is based on Diophantine approxi
mation\, and I will explain why Ostrowski representations are ``everything
one could wish for''.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/131
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwenaël Richomme
DTSTART:20260317T140000Z
DTEND:20260317T150000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/132
DESCRIPTION:Title: On some 2-binomial coefficients of binary words: geo
metrical interpretation\, partitions of integers\, and fair words\nby
Gwenaël Richomme as part of One World Combinatorics on Words Seminar\n\n\
nAbstract\nThe binomial notation $\\binom{w}{u}$ represents the number of
occurrences of the word\n$u$ as a (scattered) subword in $w$. We first int
roduce and study possible uses of\na geometrical interpretation of $\\bino
m{w}{ab}$ and \\binom{w}{ba} when $a$ and $b$ are distinct\nletters. We th
en study the structure of the $2$-binomial equivalence class of a\nbinary
word $w$ (two words are $2$-binomially equivalent if they have the same\nb
inomial coefficients\, that is\, the same numbers of occurrences\, for eac
h word\nof length at most $2$). Especially we explain the existence of an
isomorphism\nbetween the graph of the $2$-binomial equivalence class of $w
$ with respect to a\nparticular rewriting rule and the lattice of partitio
ns of the integer \\binom{w}{ab}\nwith \\binom{w}{a} parts and greatest pa
rt bounded by \\binom{w}{b}. Finally we study binary\nfair words\, the wor
ds over $\\{a\, b\\}$ having the same numbers of occurrences of $ab$\nand
$ba$ as subwords $(\\binom{w}{ab} = \\binom{w}{ba})$. In particular\, we s
ketch a proof of a recent\nconjecture related to a special case of the lea
st square approximation.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/132
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Paulina Cecchi Bernales
DTSTART:20260331T130000Z
DTEND:20260331T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/133
DESCRIPTION:Title: Interplay between combinatorics and dynamical proper
ties in minimal symbolic systems\nby Paulina Cecchi Bernales as part o
f One World 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 acti
on of the (left) shift transformation. As infinite words\, the elements of
a symbolic system possess combinatorial properties associated with their
language\, and it is natural to ask how these combinatorial properties det
ermine or interact with the properties of the system as a dynamical system
\, or vice versa. In this talk\, I will briefly review the basic notions o
f symbolic systems and some classical results which connect their combinat
orial and dynamical properties\, particularly for subshifts generated by s
ubstitutions. I will then present more recent results illustrating the imp
act of combinatorics on the spectral properties of minimal subshifts. In t
hese results\, combinatorial objects such as extension graphs or coboundar
ies will play an important role. This is a part of a joint work with V. Be
rthé and B. Espinoza.\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/133
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Idrissa Kaboré
DTSTART:20260414T130000Z
DTEND:20260414T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/134
DESCRIPTION:by Idrissa Kaboré as part of One World Combinatorics on Words
Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/134
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ľubomíra Dvořáková
DTSTART:20260428T130000Z
DTEND:20260428T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/135
DESCRIPTION:by Ľubomíra Dvořáková as part of One World Combinatorics
on Words Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/135
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Léo Vivion
DTSTART:20260512T130000Z
DTEND:20260512T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/136
DESCRIPTION:by Léo Vivion as part of One World Combinatorics on Words Sem
inar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/136
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Reem Yassawi
DTSTART:20260526T130000Z
DTEND:20260526T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/137
DESCRIPTION:by Reem Yassawi as part of One World Combinatorics on Words Se
minar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/137
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bastiàn Espinoza
DTSTART:20260609T130000Z
DTEND:20260609T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/138
DESCRIPTION:by Bastiàn Espinoza as part of One World Combinatorics on Wor
ds Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/138
/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Delaram Moradi
DTSTART:20260707T130000Z
DTEND:20260707T140000Z
DTSTAMP:20260404T110833Z
UID:CombinatoricsOnWords/139
DESCRIPTION:by Delaram Moradi as part of One World Combinatorics on Words
Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CombinatoricsOnWords/139
/
END:VEVENT
END:VCALENDAR