BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Lucas Mol (University of Winnipeg)
DTSTART;VALUE=DATE-TIME:20200629T130000Z
DTEND;VALUE=DATE-TIME:20200629T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/1
DESCRIPTION:Title: Extremal Square-Free Words and Variations\nby Lucas Mol (
University of Winnipeg) as part of One World Combinatorics on Words Semina
r\n\n\nAbstract\nA square-free word $w$ over a fixed alphabet $\\Sigma$ is
extremal if every word obtained from $w$ by inserting a single letter fro
m $\\Sigma$ (at any position) contains a square. Grytczuk et al. recently
introduced the concept of extremal square-free word\, and demonstrated tha
t there are arbitrarily long extremal square-free words over a ternary alp
habet. One can define extremal overlap-free words\, and more generally\, e
xtremal $\\beta$-free words\, analogously. We characterize the lengths of
extremal square-free ternary words\, and the lengths of extremal overlap-f
ree binary words. We also establish that there are arbitrarily long extrem
al $\\beta$-free binary words for every $2 < \\beta \\leq 8/3$. We include
a variety of interesting conjectures and open questions.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Rigo (University of Liège)
DTSTART;VALUE=DATE-TIME:20200713T130000Z
DTEND;VALUE=DATE-TIME:20200713T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/2
DESCRIPTION:Title: Binomial^3 : coefficients\, equivalence\, complexity…\
nby Michel Rigo (University of Liège) as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nThe binomial coefficient $x \\choose y$ of
the words $x$ and $y$ is the number of times $y$ appears as a (scattered)
subword of $x$. This concept has received a lot of attention\, e.g.\, Sim
on's congruence\, Parikh matrices\, reconstruction problem\, ... A few yea
rs ago\, we introduced the $k$-binomial equivalence: Two words $u$ and $v$
are $k$-binomially equivalent if the binomial coefficients $u \\choose x$
and $v \\choose x$ agree for all words $x$ of length up to $k$. This is a
refinement of the usual abelian equivalence.\n\nFirst\, I will review sev
eral results (joint work with P. Salimov\, M. Lejeune\, J. Leroy\, M. Rose
nfeld) related to $k$-binomial complexity (where factors of length $n$ are
counted up to $k$-binomial equivalence) for Sturmian words\, Thue-Morse w
ord and Tribonacci word. Then I will concentrate on $k$-binomial equivalen
ce classes for finite words. In particular\, I will discuss the fact that
the submonoid generated by the generators of the free nil-$2$ group on $m$
generators is isomorphic to the quotient of the free monoid $\\{1\,...\,m
\\}^∗$ by the $2$-binomial equivalence (joint work with M. Lejeune\, M.
Rosenfeld).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laurent Vuillon (University of Savoie)
DTSTART;VALUE=DATE-TIME:20200720T130000Z
DTEND;VALUE=DATE-TIME:20200720T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/3
DESCRIPTION:Title: Combinatorics on words for Markoff numbers\nby Laurent Vu
illon (University of Savoie) as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nMarkoff numbers are fascinating integers related to
number\ntheory\, Diophantine equation\, hyperbolic geometry\, continued fr
actions\nand Christoffel words. Many great mathematicians have worked on t
hese\nnumbers and the $100$ years famous uniqueness conjecture by Frobeniu
s is\nstill unsolved. In this talk\, we state a new formula to compute the
\nMarkoff numbers using iterated palindromic closure and the Thue-Morse\ns
ubstitution. The main theorem shows that for each Markoff number $m$\,\nth
ere exists a word $v\\in \\{a\,b\\}^*$ such that $m−2$ is equal to the l
ength of the iterated palindromic\nclosure of the iterated antipalindromic
closure of the word $av$. This\nconstruction gives a new recursive constr
uction of the Markoff numbers\nby the lengths of the words involved in the
palindromic closure.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:James Currie (University of Winnipeg)
DTSTART;VALUE=DATE-TIME:20200727T130000Z
DTEND;VALUE=DATE-TIME:20200727T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/4
DESCRIPTION:Title: Remarks on Pansiot encodings\nby James Currie (University
of Winnipeg) as part of One World Combinatorics on Words Seminar\n\n\nAbs
tract\nPansiot encodings were an essential ingredient in the solution of D
ejean's conjecture. We discuss these encodings\, and the related group the
oretic notions\, in a way perhaps more natural to combinatorics on words\,
namely\, in terms of De Bruijn graphs. We discuss variations on Pansiot e
ncodings\, with applications to circular words\, and to the undirected thr
eshold problem.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Reem Yassawi (The Open University)
DTSTART;VALUE=DATE-TIME:20200914T130000Z
DTEND;VALUE=DATE-TIME:20200914T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/5
DESCRIPTION:Title: The Ellis semigroup of bijective substitution shifts\nby
Reem Yassawi (The Open University) as part of One World Combinatorics on W
ords Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jarkko Peltomäki (University of Turku)
DTSTART;VALUE=DATE-TIME:20200928T130000Z
DTEND;VALUE=DATE-TIME:20200928T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/6
DESCRIPTION:Title: Avoiding abelian powers cyclically\nby Jarkko Peltomäki
(University of Turku) as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nA finite word $w$ avoids abelian $N$-powers cyclically if f
or each\nabelian $N$-power of period $m$\, we have $m \\geq |w|$. This not
ion\ngeneralizes circular avoidance of $N$-powers in two ways. Firstly\n"p
ower" is replaced by "abelian power" and secondly circular avoidance\nconc
erns only the conjugacy class of a word\, but here we require even\nmore.
Let $\\mathcal{A}(k)$ be the least integer $N$ such that for all\n$n$ ther
e exists a word of length $n$ over a $k$-letter alphabet that\navoids abel
ian $N$-powers cyclically. Let $\\mathcal{A}_\\infty(k)$ be the\nleast int
eger $N$ such that there exist arbitrarily long words over a\n$k$-letter a
lphabet that avoid abelian $N$-powers cyclically.\n\nI will sketch the pro
ofs of the following results: 1) $5 \\leq\n\\mathcal{A}(2) \\leq 8$\, $3 \
\leq \\mathcal{A}(3) \\leq 4$\, $2 \\leq\n\\mathcal{A}(4) \\leq 3$\, $\\ma
thcal{A}(k) = 2$ for $k \\geq 5$\; 2)\n$\\mathcal{A}_\\infty(2) = 4$\, $\\
mathcal{A}_\\infty(3) = 3$\, and\n$\\mathcal{A}_\\infty(4) = 2$. If time p
ermits\, I will discuss an\napplication to the growth rates of exponents o
f abelian powers occurring\nin infinite binary words.\n\nSorry\, no video
available\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jarosław Grytczuk (The Jagiellonian University)
DTSTART;VALUE=DATE-TIME:20201005T130000Z
DTEND;VALUE=DATE-TIME:20201005T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/7
DESCRIPTION:Title: Graph Coloring and Combinatorics on Words\nby Jarosław G
rytczuk (The Jagiellonian University) as part of One World Combinatorics o
n Words Seminar\n\n\nAbstract\nI will present a few problems inspired mutu
ally by various issues studied in the two disciplines of the title. For in
stance\, given any sequence of 3-letter alphabets\, is it possible to pick
a letter from each alphabet so that the resulting word is {\\it square-fr
ee}? The case of equal alphabets is covered by the famous result of Thue\,
but intuition tells us that this should be the hardest case (the more dif
ferent letters in the play\, the easier to avoid repeated factors). While
more than one has attacked the problem\, the question remains unanswered\,
which is especially frustrating as it has a positive answer with 4-letter
alphabets.\n\nThe above question was originally motivated by the {\\it li
st coloring} problem\, a very popular topic in graph coloring. However\, t
he opposite direction of inspiration also leads to intriguing matters. For
example\, how many letters are needed to label the vertices of a {\\it pl
anar graph} so that any word occurring along a simple path is square-free?
It has been recently proved that 768 letters suffice\, but for a long tim
e it was not known if any finite alphabet will do. Perhaps results of that
type could be applied back to some pattern avoidability issues...?\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Dekking (Technische Universiteit Delft)
DTSTART;VALUE=DATE-TIME:20201019T130000Z
DTEND;VALUE=DATE-TIME:20201019T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/8
DESCRIPTION:Title: The structure of Zeckendorf representations and base $\\varph
i$ expansions\nby Michel Dekking (Technische Universiteit Delft) as pa
rt of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn the Zecke
ndorf numeration system natural numbers are represented as sums of Fibonac
ci numbers. In base $\\varphi$ natural numbers are represented as sums of
powers of the golden mean $\\varphi$. Both representations have digits 0 a
nd 1\, where the word 11 is not allowed. We know that the Fibonacci number
s\, and the powers of $\\varphi$ are closely related\, as\, for example\,
in the relation $\\varphi^n=F_{n-1}+F_n\\varphi$. In fact\, Frougny and Sa
karovitch have shown that Zeckendorf representations can be transformed to
base $\\varphi$ expansions by a 2-tape automaton. I will take a direct ap
proach: what are the words that can occur in the Zeckendorf representation
s\, and what are those that occur in base $\\varphi$ expansions? In which
representations/expansions\, of which natural numbers do they occur?\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthieu Rosenfeld (LIS\, Marseille\, France)
DTSTART;VALUE=DATE-TIME:20201026T140000Z
DTEND;VALUE=DATE-TIME:20201026T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/9
DESCRIPTION:Title: A simple proof technique to study avoidability of repetitions
\nby Matthieu Rosenfeld (LIS\, Marseille\, France) as part of One Worl
d Combinatorics on Words Seminar\n\n\nAbstract\nI recently described a new
proof technique that I used to study nonrepetitive colorings of graphs. T
his technique is in fact more general and seems to be as powerful as the L
ovász local lemma or the entropy compression method. For instance\, it h
as since been used by D.R. Wood and I.M. Wanless in the context of boolea
n satisfiability problem and of hypergraph colorings. In the particular co
ntext of combinatorics on words similar approaches had already been used b
y different authors\, but were never extended to graphs or other structure
s.\n\nIn this talk\, I will first present some simple applications of the
method to combinatorics on words and I will then explain how to extend thi
s approach to nonrepetitive colorings of graphs of bounded degree.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Eric Rowland (Hofstra University)
DTSTART;VALUE=DATE-TIME:20201109T140000Z
DTEND;VALUE=DATE-TIME:20201109T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/10
DESCRIPTION:Title: Avoiding fractional powers on an infinite alphabet\nby E
ric Rowland (Hofstra University) as part of One World Combinatorics on Wor
ds Seminar\n\n\nAbstract\nQuestions concerning avoidability of patterns ha
ve been central to combinatorics on words since the work of Thue. In 2009\
, Guay-Paquet and Shallit gave several results about pattern avoidance of
words on the alphabet of natural numbers. Most patterns are avoidable on t
his alphabet\, but it is interesting to ask about the lexicographically le
ast word that avoids a pattern. For fractional powers\, often this word is
generated by a relatively simple morphism. In recent work with Manon Stip
ulanti\, we discovered the structure of the lexicographically least 5/4-po
wer-free word on the natural numbers. In a surprising departure from previ
ously studied words\, the morphism generating this word does not preserve
5/4-power-freeness.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Émilie Charlier (University of Liège)
DTSTART;VALUE=DATE-TIME:20201123T140000Z
DTEND;VALUE=DATE-TIME:20201123T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/11
DESCRIPTION:Title: Regular sequences in abstract numeration systems\nby Ém
ilie Charlier (University of Liège) as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nAn abstract numeration system $S$ is given b
y a regular language $L$ over a totally ordered alphabet $(A\,<)$. The num
eration language $L$ is ordered thanks to the radix (or genealogical) orde
r induced by $<$. A natural number $n$ is then represented by the $n$-th w
ord of the language (where we start counting from $n=0$). Integer bases $b
$ and numeration systems based on a linear base sequence $U$ with a regula
r numeration language are examples of abstract numeration systems. The not
ion of $b$-regular sequences was extended to abstract numeration systems b
y Maes and Rigo. Their definition is based on a notion of $S$-kernel that
extends that of $b$-kernel. However\, this definition does not allow us to
generalize all of the many characterizations of $b$-regular sequences. In
this talk\, I will present an alternative definition of $S$-kernel\, and
hence an alternative definition of $S$-regular sequences\, that permits us
to use recognizable formal series in order to generalize most (if not all
) known characterizations of $b$-regular sequences. I will also show that
an extra characterization can be obtained in the case of Pisot numeration
systems. Finally\, I will consider the special cases of $S$-automatic and
$S$-synchronized sequences. In particular\, we will see that the factor co
mplexity of an $S$-automatic sequence defines an $S$-regular sequence. Thi
s is a joint work with Célia Cisternino and Manon Stipulanti.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marie Lejeune (University of Liège)
DTSTART;VALUE=DATE-TIME:20201207T140000Z
DTEND;VALUE=DATE-TIME:20201207T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/12
DESCRIPTION:Title: Reconstructing words from right-bounded-block words\nby
Marie Lejeune (University of Liège) as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nIn this joint work with P. Fleischmann\, F.
Manea\, D. Nowotka\, and M. Rigo\, we study a variation of the famous reco
nstruction problem over words. It has been studied since $1973$. A survey
of the different results will be held in the talk.\n\nWe study a variation
of this problem.\nLet $\\mathcal{A}$ be a given alphabet and $n$ a natura
l number. We want to reconstruct a hidden word $w \\in \\mathcal{A}^n$. To
that aim\, we are allowed to pick a word $u_i$ and ask questions of the t
ype "What is the multiplicity of $u_i$ as subword of $w$?". Based on the a
nswers to questions related to words $u_1\, \\ldots\, u_i$\, we can decide
which will be the next question (i.e. decide which word will be $u_{i+1}$
). We want to have the shortest sequence $(u_1\, \\ldots\, u_k)$ uniquely
determining $w$.\n\nWe naturally look for a value of $k$ less than the upp
er known bound for $k$-reconstructibility.\n\nWe will show how to reconstr
uct a binary word $w$ from $m+1$ questions\, where $m$ is the minimum numb
er of occurrences of {\\tt a} and {\\tt b} in the word. We then reduce the
problem for arbitrary finite alphabets to the binary case. We compare our
bounds to the best known one for the classical reconstruction problem.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sébastien Labbé (LaBRI\, Bordeaux\, France)
DTSTART;VALUE=DATE-TIME:20201214T140000Z
DTEND;VALUE=DATE-TIME:20201214T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/13
DESCRIPTION:Title: A characterization of Sturmian sequences by indistinguishabl
e asymptotic pairs\nby Sébastien Labbé (LaBRI\, Bordeaux\, France) a
s part of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe give
a new characterization of Sturmian configurations in terms of indistinguis
hable asymptotic pairs. Two asymptotic configurations on a full $\\mathbb{
Z}$-shift are indistinguishable if the sets of occurrences of every patter
n in each configuration coincide up to a finitely supported permutation. T
his characterization can be seen as an extension to biinfinite sequences o
f Pirillo's theorem which characterizes Christoffel words. Furthermore\, w
e provide a full characterization of indistinguishable asymptotic pairs on
arbitrary alphabets using substitutions and characteristic Sturmian seque
nces. The proof is based on the well-known notion of derived sequences.\n\
nThis is joint work with Sebastián Barbieri and Štěpán Starosta. Prepr
int is available at https://arxiv.org/abs/2011.08112\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anna Frid (Aix-Marseille Université)
DTSTART;VALUE=DATE-TIME:20210104T140000Z
DTEND;VALUE=DATE-TIME:20210104T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/14
DESCRIPTION:Title: Is not prefix palindromic length of a k -automatic word k
-regular?\nby Anna Frid (Aix-Marseille Université) as part of One Wor
ld Combinatorics on Words Seminar\n\n\nAbstract\nWe consider the function
of the prefix palindromic length for $k$-automatic words and prove that it
is $k$-regular for such words containing a finite number of distinct pali
ndromes\, like for example the paperfolding word. We also observe that in
the opposite case\, if the number of distinct palindromes is infinite\, th
is function can be $k$-regular\, as for the Thue-Morse word\, or seemingly
not\, as for the period-doubling word. The fact of non-regularity\, howev
er\, stays unproven.\n\nThis is a joint work with Enzo Laborde and Jarkko
Peltomäki.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean-Paul Allouche (CNRS\, IMJ-PRG\, Sorbonne Université\, Paris)
DTSTART;VALUE=DATE-TIME:20210201T140000Z
DTEND;VALUE=DATE-TIME:20210201T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/16
DESCRIPTION:Title: Hidden automatic sequences\nby Jean-Paul Allouche (CNRS\
, IMJ-PRG\, Sorbonne Université\, Paris) as part of One World Combinatori
cs on Words Seminar\n\n\nAbstract\nWe discuss a joint work with Michel Dek
king and Martine Queffélec (https://arxiv.org/abs/2010.00920) about seque
nces given as fixed points of non-uniform morphisms that happen to be actu
ally automatic.\n\nOne of the most ancien example is probably the one due
to Berstel\, who proved that the Istrail squarefree sequence defined as th
e fixed point of the morphism $f$ with $f(0) = 12$\, $f(1) = 102$\, $f(2)
= 0$ is also\n$2$-automatic.\n\nAfter revisiting an old criterion due to M
. Dekking at the end of the 70's\, we give several examples (in particular
of sequences in the OEIS). Finally we focus on morphisms associated with
Grigorchuk(-like) groups.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Petr Ambrož
DTSTART;VALUE=DATE-TIME:20210215T140000Z
DTEND;VALUE=DATE-TIME:20210215T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/17
DESCRIPTION:Title: Morphisms generating antipalindromic words\nby Petr Ambr
ož as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe
introduce two classes of morphisms over the alphabet\n$A=\\{0\,1\\}$ whose
fixed\npoints contain infinitely many antipalindromic factors. An\nantipa
lindrome is a finite word invariant\nunder the action of the antimorphism
$E:\\{0\,1\\}^*\\to\\{0\,1\\}^*$\, defined\nby $E(w_1\\cdots w_n)=(1-w_n)\
\cdots(1-w_1)$.\nWe conjecture that these two classes contain all morphism
s (up to\nconjugation) which generate infinite words with\ninfinitely many
antipalindromes. This is an analogue to the famous HKS\nconjecture concer
ning infinite words\ncontaining infinitely many palindromes. We prove our
conjecture for two\nspecial classes of morphisms\,\nnamely (i) uniform mor
phisms and (ii) morphisms with fixed points\ncontaining also infinitely ma
ny palindromes.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mickaël Postic
DTSTART;VALUE=DATE-TIME:20210301T140000Z
DTEND;VALUE=DATE-TIME:20210301T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/18
DESCRIPTION:Title: Open and closed complexity functions of infinite words\n
by Mickaël Postic as part of One World Combinatorics on Words Seminar\n\n
\nAbstract\nClosed words\, also known as complete first returns\, have bee
n studied for a long time\, and play an important role in symbolic dynamic
s. A word which is not closed is said to be open. In this talk based on a
joint work with Olga Parshina\, I will present a characterization of aperi
odic words in terms of their open complexity function and closed complexit
y function\, in the spirit of Morse and Hedlund's theorem. The preprint is
available at https://arxiv.org/pdf/2005.06254.pdf\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Szymon Stankiewicz
DTSTART;VALUE=DATE-TIME:20210315T140000Z
DTEND;VALUE=DATE-TIME:20210315T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/19
DESCRIPTION:Title: Square-free reducts of words\nby Szymon Stankiewicz as p
art of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe discuss
a joint work with Jarosław Grytczuk (https://arxiv.org/abs/2011.12822) ab
out square-free reducts of words.\n\nIn any finite word one may delete the
repeated block of a square\, obtaining thereby a shorter word. By repeati
ng this process\, a square-free word is eventually reached\, which we call
a reduct of the original word.\n\nWe will show that for each positive int
eger $n$ there is a word over ternary alphabet which can be reduced to at
least $n$ different words and also that there is a word over alphabet of s
ize four which has exactly $n$ reducts. We will also show that there exist
s infinitely many ternary words having exponential many reducts in the len
gth of these words.\n\nFor a fixed alphabet one can create a poset with no
des being words and $u > v$ iff word $u$ can be reduced to word $v$. We wi
ll describe some properties of those posets.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jacques Sakarovitch (RIF\, CNRS / Univ. de Paris and Télécom Par
is\, IPP)
DTSTART;VALUE=DATE-TIME:20210329T130000Z
DTEND;VALUE=DATE-TIME:20210329T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/20
DESCRIPTION:Title: From Fibonacci to golden mean representations\nby Jacque
s Sakarovitch (RIF\, CNRS / Univ. de Paris and Télécom Paris\, IPP) as p
art of One World Combinatorics on Words Seminar\n\n\nAbstract\nEvery posit
ive integer can be written as a sum of Fibonacci numbers\; this yields a F
ibonacci representation of the integer. A positive integer can also be wri
tten as a (finite) sum of (positive and negative) powers of the golden mea
n\; this yields a golden mean representation of the integer\, with the rad
ix point roughly in the middle of the writing. It is the golden mean expan
sion when it contains no consecutive digits equal to 1.\n\nWe show that th
ere exists a letter-to-letter finite two-tape automaton that maps the Fibo
nacci representation of any positive integer onto its golden mean expansio
n\, provided the latter is folded around the radix point. As a corollary\,
the set of golden mean expansions of the positive integers is a linear co
ntext-free language.\n\nThese results are generalised to the more general
case of integer representations in numeration systems built upon quadratic
Pisot units.\n\nJoint work with Christiane Frougny\, published in 1999 in
the Journal of Algebra and Computation. This talk is a follow-up to the o
ne of October 15 by Michel Dekking\, who kindly quoted this paper but deem
ed it hard to understand.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Valérie Goyheneche
DTSTART;VALUE=DATE-TIME:20210412T130000Z
DTEND;VALUE=DATE-TIME:20210412T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/21
DESCRIPTION:Title: Eigenvalues and constant arithmetical progressions for subst
itutive sequences\nby Valérie Goyheneche as part of One World Combina
torics on Words Seminar\n\n\nAbstract\nThe main subject of this talk is to
answer the following decidability question : does a substitutive sequence
$x$ admit a constant arithmetical progression $(x_{k+np})_n$?\n\nOur meth
od mainly relies on the link between constant arithmetical subsequences an
d (dynamical) eigenvalues of the underlying dynamical system.\nWe will exp
lain a method to compute the set of (additive) eigenvalues associated to s
uch systems.\nWe can then deduce\, given an integer $p$\, if the sequence
$x$ contains a constant arithmetical progression with period $p$.\nAt the
end of the talk\, we will focus on the case of primitive constant-length s
ubstitutions\, for which the set of such periods can be described by an au
tomaton.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luca Zamboni
DTSTART;VALUE=DATE-TIME:20210426T130000Z
DTEND;VALUE=DATE-TIME:20210426T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/22
DESCRIPTION:Title: Singular words\nby Luca Zamboni as part of One World Com
binatorics on Words Seminar\n\n\nAbstract\nThe extremal solutions to certa
in problems in the theory of finite continued fractions are characterised
by a special combinatorial property which we call the _singular_ property.
This property may be interpreted in the framework of finite words\, cycli
c words\, and one and two-sided infinite words over arbitrary ordered alph
abets. Each linear (resp. cyclic) word w is Abelian equivalent to a singul
ar linear (resp. cyclic) word w’ which is in general unique up to revers
al. We develop an algorithm for generating all singular words having a pr
escribed Parikh vector which is based in part on a non-commutative variant
of the usual Euclidean algorithm. This allows us to answer a question of
G. Ramharter from 1983 on the extremal values of the regular and semi-regu
lar cyclic continuants introduced by Motzkin and Straus in the 1950’s. W
e also confirm a conjecture of Ramharter in certain instances and exhibit
counter examples in other cases. As for infinite words\, the singular pro
perty in the context of bi-infinite binary words coincides with the Markof
f property which was shown by C. Reutenauer to be equivalent to the balanc
e property. We generalise this to higher alphabets by showing that the si
ngular property is the fundamental property which characterises the langu
age structure of codings of symmetric k-interval exchange transformations.
This is based on a collaboration with Alessandro De Luca and Marcia Edso
n initiated during the first Covid lockdown of 2020.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robert Mercas (Loughborough University)
DTSTART;VALUE=DATE-TIME:20210208T140000Z
DTEND;VALUE=DATE-TIME:20210208T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/23
DESCRIPTION:Title: (Trying to do a) Counting of distinct repetitions in words\nby Robert Mercas (Loughborough University) as part of One World Combin
atorics on Words Seminar\n\n\nAbstract\nThe topic of counting the distinct
repetitions that a word contains has been around for at least two decades
. The problem of counting distinct squares in a word was introduced by Fra
enkel and Simpson in ’98\, who also showed that their number is upper bo
unded by twice the length of the word. However\, their conjecture that the
factor of 2 is superfluous (the length of the word is a strict bound) is
still open (though there exist several improvements of their original resu
lt). Moreover\, recently Manea and Seki showed that proving the bound for
binary words is enough. Moreover\, further work was done on counting disti
nct repetitions of higher exponent with quite sharp bounds.\nBy looking at
non-extendable repetitions of power at least two (thus considering fracti
onal ones as well) Kolpakov and Kucherov tried to bound in ‘99 the numbe
r of runs in a word (non-necessarily distinct). This was recently shown to
be less than the length $n$ of the word that we consider and more than 0.
9482 times $n$. \nHowever\, all of these ideas have a common sticking poin
t\, namely the three squares lemma of Crochemore and Rytter\, which they a
ll use as main tool. In this talk I will present a different technique (wh
ich so far is not fully exploited) of trying to count distinct squares and
show some surprising connections between all of the above notions.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:M. Andrieu\, C. Cisterino\, L. Dvořáková\, Š. Holub\, F. Manea
\, C. Reutenauer
DTSTART;VALUE=DATE-TIME:20210222T140000Z
DTEND;VALUE=DATE-TIME:20210222T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/24
DESCRIPTION:Title: Day of short talks\nby M. Andrieu\, C. Cisterino\, L. Dv
ořáková\, Š. Holub\, F. Manea\, C. Reutenauer as part of One World Com
binatorics on Words Seminar\n\n\nAbstract\n15:00 Christophe Reutenauer An
arithmetical characterization of Christoffel words\n\n15:30 Célia Cistern
ino Two applications of the composition of a \n2-tape automaton and a weig
hted automaton\n\n16:00 Lubka Dvořáková On balanced sequences with the
minimal asymptotic critical exponent\n\n16:30 Štěpán Holub Formalizatio
n of Combinatorics on Words in Isabelle/HOL\n\n17:00 Florin Manea Efficien
tly Testing Simon's Congruence\n\n17:30 Mélodie Andrieu A Rauzy fractal u
nbounded in all directions of the plane\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Day of short talks
DTSTART;VALUE=DATE-TIME:20210322T140000Z
DTEND;VALUE=DATE-TIME:20210322T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/25
DESCRIPTION:Title: Day of short talks: I. Aedo\, F. Dolce\, A. Frid\, J. Palaci
o\, J. Shallit\nby Day of short talks as part of One World Combinatori
cs on Words Seminar\n\n\nAbstract\n15:00 Jane D. Palacio\, Coverable bi-in
finite substitution shifts\n\n15:30 Ibai Aedo\, On long arithmetic progres
sions in binary Morse-like words\n\n16:00 Francesco Dolce\, On morphisms p
reserving palindromic richness\n\n16:30 Jeffrey Shallit\, Robbins and Ardi
la meet Berstel\n\n17:00 Anna E. Frid\, The semigroup of trimmed morphisms
\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwenaël Richomme
DTSTART;VALUE=DATE-TIME:20210503T130000Z
DTEND;VALUE=DATE-TIME:20210503T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/26
DESCRIPTION:Title: On sets of indefinitely desubstitutable words\nby Gwena
ël Richomme as part of One World Combinatorics on Words Seminar\n\n\nAbst
ract\nThe stable set associated to a given set $S$ of nonerasing endomorph
isms or substitutions is the set of all right infinite words that can be i
ndefinitely desubstituted over $S$. This notion generalizes the notion of
sets of fixed points of morphisms. It is linked to $S$-adicity and to prop
erty preserving morphisms. Two main questions are considered. Which known
sets of infinite words are stable sets? Which ones are stable sets of a fi
nite set of substitutions? While bringing answers to the previous question
s\, some new way of characterizing several well-known sets of words such a
s the set of binary balanced words or the set of episturmian words are pre
sented. A characterization of the set of nonerasing endomorphisms that pre
serve episturmian words is also provided.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kevin Buzzard
DTSTART;VALUE=DATE-TIME:20210510T130000Z
DTEND;VALUE=DATE-TIME:20210510T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/27
DESCRIPTION:Title: Teaching computers to prove theorems\nby Kevin Buzzard a
s part of One World Combinatorics on Words Seminar\n\n\nAbstract\nOver the
last few years I have been teaching proofs of theorems to computers\, and
teaching students how to teach proofs of theorems to computers. The Krusk
al Katona theorem is a theorem I learnt as an MSc student\, and Cambridge
PhD student Bhavik Mehta taught it to the Lean theorem prover here: https:
//b-mehta.github.io/combinatorics/ . Lean's maths library `mathlib` https:
//github.com/leanprover-community/mathlib is now half a million lines of t
heorem proofs\, many of them proved by mathematicians who have picked up t
his language\, and most of them learnt it like Bhavik\, just choosing a pr
oject and working on it. I will talk about how I learnt Lean\, how you can
learn Lean\, what the point of learning Lean is\, what the point of teach
ing Lean is\, and where all this stuff might end up going. Rest assured --
I will not assume any prior familiarity with computer theorem provers in
this talk!\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeffrey Shallit
DTSTART;VALUE=DATE-TIME:20210517T130000Z
DTEND;VALUE=DATE-TIME:20210517T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/28
DESCRIPTION:Title: The Walnut Tutorial: Using A Tool for Doing Combinatorics o
n Words\nby Jeffrey Shallit as part of One World Combinatorics on Word
s Seminar\n\n\nAbstract\nWalnut is free open-source software\, written by
Hamoon Mousavi\, that can\nrigorously prove or disprove claims about autom
atic sequences (broadly\nunderstood)\, such as the Thue-Morse sequence\, t
he Fibonacci infinite\nword\, and others. It can also be used to create e
xplicit formulas for\nvarious aspects of such sequences\, such as subword
complexity\,\npalindrome complexity\, and so forth.\n\nIn this talk I won'
t discuss how it works. Instead I'll give a\ntutorial\, surveying the ki
nds of things you can and can't do with it.\nWe'll "get our hands dirty" a
nd solve problems in real time.\n\nAt the end\, if there's time\, I'll sol
icit problems about such sequences\nfrom the audience and try to solve the
m with Walnut. Come prepared with\nsome conjecture you haven't been able
to prove yet!\n\nThe tutorial will last about 90 minutes.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Etienne Moutot
DTSTART;VALUE=DATE-TIME:20210531T130000Z
DTEND;VALUE=DATE-TIME:20210531T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/29
DESCRIPTION:Title: Recent advances around Nivat's conjecture\nby Etienne Mo
utot as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nNi
vat's conjecture states that any two dimensional word with "low enough" pa
ttern complexity must be periodic.\nEven if the statement of the conjectur
e is quite simple and very similar to the one dimensional Morse-Hedlund th
eorem\, the conjecture is still open since stated by Maurice Nivat in 1997
. However\, there have been a lot of progress towards a proof in the last
five years\, and many new tools started to emerge. In 2015\, Cyr and Kra s
tarted to use tools from symbolic dynamics to improve the bound required t
o prove periodicity. At about the same time\, Jarkko Kari and Michal Szaba
dos started to develop an algebraic approach to tackle the conjecture\, le
ading to very elegant proofs of new results related to Nivat's conjecture.
\n\nIn this talk I will present the conjecture and some of the last result
s around it. I will then focus on the algebraic approach initiated by Kari
and Szabados.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pascal Ochem
DTSTART;VALUE=DATE-TIME:20210607T130000Z
DTEND;VALUE=DATE-TIME:20210607T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/30
DESCRIPTION:Title: Avoiding large squares in trees and planar graphs\nby Pa
scal Ochem as part of One World Combinatorics on Words Seminar\n\n\nAbstra
ct\nThe Thue number $T(G)$ of a graph $G$ is the minimum number of colors
needed to color $G$ without creating a square on a path of $G$. For a grap
h class $C$\, $T(C)$ is the supremum of $T(G)$ over the graphs $G$ in $C$.
\nThe Thue number has been investigated for famous minor-closed classes:\n
$T(tree) = 4$\, $7 \\leq T(outerplanar) \\leq 12$\, $11 \\leq T(planar)
\\leq 768$.\nFollowing a suggestion of Grytczuk\, we consider the generali
sed parameters $T_k(C)$ such that only squares of period at least $k$\nmus
t be avoided. Thus\, $T(C) = T_1(C)$.\nWe show that $T_2(tree) = 3$\, $T_5
(tree) = 2$\, and $T_k(planar) \\geq 11$ for every fixed $k$.\nThis is a j
oint work with Daniel Gonçalves and Matthieu Rosenfeld.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Golnaz Badkobeh
DTSTART;VALUE=DATE-TIME:20210614T130000Z
DTEND;VALUE=DATE-TIME:20210614T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/31
DESCRIPTION:Title: Left Lyndon tree construction\nby Golnaz Badkobeh as par
t of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe extend the
left-to-right Lyndon factorisation of a word to the left Lyndon tree cons
truction of a Lyndon word. It yields an algorithm to sort the prefixes of
a Lyndon word according to the infinite ordering defined by Dolce et al. (
2019). A straightforward variant computes the left Lyndon forest of a word
. All algorithms run in linear time in the letter-comparison model.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Florin Manea
DTSTART;VALUE=DATE-TIME:20210628T130000Z
DTEND;VALUE=DATE-TIME:20210628T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/32
DESCRIPTION:Title: Efficiently testing Simon's congruence\nby Florin Manea
as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn this
talk\, we will cover a series of recent algorithmic results related to th
e processing of subsequences occurring in words. Firstly\, we will show ho
w to test in linear time whether two given words have exactly the same set
of subsequences of length $k$ (or\, in other words\, whether they are $k$
-equivalent w.r.t. the Simon congruence)\, where $k$ is a positive integer
also given as input. Secondly\, we show how to compute in linear time\, f
or two given words\, which is the largest positive integer $k$ for which t
he two words are $k$-Simon-congruent. We will conclude this talk with a se
ries of related results. On the one hand\, we consider the problem of tran
sforming words by edit operations so that they become Simon-congruent and\
, on the other hand\, we consider the notion of absent subsequences in wor
ds and problems related to this.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Štěpán Holub
DTSTART;VALUE=DATE-TIME:20210712T130000Z
DTEND;VALUE=DATE-TIME:20210712T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/33
DESCRIPTION:Title: Using Isabelle/HOL in Combinatorics on Words research\nb
y Štěpán Holub as part of One World Combinatorics on Words Seminar\n\n\
nAbstract\nIn this talk I will introduce a (growing) library of results in
Combinatorics on Words formalized in the proof assistant Isabelle/HOL. I
will emphasize the practical use of this library by a beginner\, rather th
an theoretical aspects of either the proof assistant or the formalized res
ults. The participants are therefore strongly encouraged to try Isabelle a
long with me during my talk\, which requires to have Isabelle installed\,
as well as the draft version of our formalization downloaded. Questions st
emming from your own attempts are most welcome\, independently of how naï
ve they may seem.\n\nFor an installation guide\, visit\nhttps://gitlab.com
/formalcow/combinatorics-on-words-formalized#a-short-guide-for-isabellehol
-beginners-how-to-formalize-your-combinatorics-on-words-result\nEverything
should be straightforward. If you encounter any problem\, you can write m
e to holub@karlin.mff.cuni.cz.\nIssues with the installation can be also a
ddressed during the preliminary technical session: I will be available 20
minutes before the official start.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jason Bell
DTSTART;VALUE=DATE-TIME:20210726T130000Z
DTEND;VALUE=DATE-TIME:20210726T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/34
DESCRIPTION:Title: Lie complexity of words\nby Jason Bell as part of One Wo
rld Combinatorics on Words Seminar\n\n\nAbstract\nGiven a right-infinite w
ord $\\bf{w}$ over a finite alphabet\, we introduce a new complexity funct
ion $L_{\\bf w}(n)$\, motivated by the theory of Lie algebras\, whose valu
e at $n$ is the number of equivalence classes of factors $x$ of ${\\bf w}$
of length $n$ with the property that every cyclic permutation of $x$ is a
gain a factor of ${\\bf w}$\, where two words $x$ and $y$ are equivalent i
f there exist words $a$ and $b$ such that $x=ab$ and $y=ba$. We show that
the Lie complexity function is uniformly bounded for words ${\\bf w}$ of
linear factor complexity and that it is a $k$-automatic sequence when ${\\
bf w}$ is $k$-automatic. As a consequence of these results we can show th
at if ${\\bf w}$ is a word of linear factor complexity then there are only
finitely many primitive factors $v$ of ${\\bf w}$ with the property that
$v^n$ is a factor of ${\\bf w}$ for every $n\\ge 1$. We also consider ext
ensions of these results. This is joint work with Jeffrey Shallit.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Day of Short Talks
DTSTART;VALUE=DATE-TIME:20210621T130000Z
DTEND;VALUE=DATE-TIME:20210621T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/35
DESCRIPTION:Title: Jakub Byszewski\, Jarosław Duda\, Jarkko Peltomäki\, Palak
Pandoh\, Clément Lagisquet\, Bartłomiej Pawlik\nby Day of Short Tal
ks as part of One World Combinatorics on Words Seminar\n\n\nAbstract\n15:0
0 Jakub Byszewski\, Automata and finite order automorphisms of the power s
eries ring\n\n15:30 Jarosław Duda\, Generalized Fibonacci coding problem
using Maximal Entropy Random Walk and Asymmetric Numeral Systems\n\n16:00
Jarkko Peltomäki\, Initial nonrepetitive complexity of regular episturmia
n words and their Diophantine exponents\n\n16:30 Palak Pandoh\, Counting s
cattered palindromes in a finite word\n\n17:00 Clément Lagisquet\, (LAMA)
On Markov Numbers: An answer to three conjectures from Aigner\n\n17:30 Ba
rtłomiej Pawlik\, Nonchalant procedure\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Arseny Shur
DTSTART;VALUE=DATE-TIME:20210927T130000Z
DTEND;VALUE=DATE-TIME:20210927T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/36
DESCRIPTION:Title: Abelian repetition threshold revisited\nby Arseny Shur a
s part of One World Combinatorics on Words Seminar\n\n\nAbstract\nAbelian
repetition threshold ART$(k)$ is the number separating fractional Abelian
powers which are avoidable and unavoidable over the $k$-letter alphabet. I
n contrast with the «usual» repetition threshold RT$(k)$\, no exact valu
es of ART$(k)$ are known. The lower bounds were proved in [A.V. Samsonov\,
A.M. Shur. On Abelian repetition threshold. RAIRO ITA\, 2012] and conject
ured to be tight. We present a method of study of Abelian power-free langu
ages using random walks in prefix trees and some experimental results obta
ined by this method. On the base of these results\, we conjecture that the
lower bounds for ART$(k)$ by Samsonov and Shur are not tight for all $k$
except for $k=5$ and prove this conjecture for $k=6\,7\,8\,9\,10$. Namely\
, we show that ART$(k)>(k-2)(k-3)$ in all these cases.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:France Gheeraert
DTSTART;VALUE=DATE-TIME:20211011T130000Z
DTEND;VALUE=DATE-TIME:20211011T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/37
DESCRIPTION:Title: $S$-adic characterization of dendric languages: ternary case
\nby France Gheeraert as part of One World Combinatorics on Words Semi
nar\n\n\nAbstract\nUniformly recurrent dendric languages generalize Arnoux
-Rauzy languages and interval exchanges and are defined via the left-\, ri
ght- and biextensions of their words. In a series of articles\, Berthé et
al. introduced them and\, among other results\, proved that this family i
s stable under derivation\, which leads to the existence of particular $S$
-adic representations.\n\nIn this talk\, we will see how we can use the pr
operties of these representations to obtain an $S$-adic characterization o
f uniformly recurrent dendric languages. We give some general results then
focus on the case of a ternary alphabet to obtain a simpler characterizat
ion.\n\nThis is a joint work with Marie Lejeune and Julien Leroy.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fabien Durand
DTSTART;VALUE=DATE-TIME:20211025T130000Z
DTEND;VALUE=DATE-TIME:20211025T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/38
DESCRIPTION:Title: Beyond substitutive sequences : Self-induced dynamical syste
ms and sequences on compact alphabets\nby Fabien Durand as part of One
World Combinatorics on Words Seminar\n\n\nAbstract\nIt is well-known that
primitive substitutions are recognizable. This property implies that the
minimal substitution subshifts $(X\,S)$ are self-induced. That is\, there
exists a clopen set $U$ included in $X$ such that $(U\,S_U)$ is isomorphic
to $(X\,S)$\, where $S_U (x)=S^n (x)$ and $n>0$ is the first iterate comi
ng back to $U$.\n\nWe will see that all dynamical systems are self-induced
in a measurable perspective.\n\nBut from a topological point of view self
induction characterizes minimal substitution subshifts on possibly infini
te alphabets (even uncountable).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dan Rust
DTSTART;VALUE=DATE-TIME:20211108T140000Z
DTEND;VALUE=DATE-TIME:20211108T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/39
DESCRIPTION:Title: Random substitutions\nby Dan Rust as part of One World C
ombinatorics on Words Seminar\n\n\nAbstract\nA random substitution is a ge
neralisation of a substitution on a finite alphabet. Whereas with classica
l substitutions\, letters have a single word as an image\, random substitu
tions have a finite set of possible image words that are independently cho
sen each time it is applied to the letters in a word. As an example\, the
`random Fibonacci substitution' is given by\n\n$$ a \\mapsto \\{ab\,ba\\}\
, b \\mapsto \\{a\\}.$$\n\nThis gives rise to languages of legal words tha
t share similar properties with substitutive words (i.e.\, hierarchical st
ructures) but which also have exponential complexity functions (entropy).
I will give an overview of this rarely explored class of systems\, some of
the aspects that have recently been studied\, and some easy-to-state open
problems.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Day of short talks
DTSTART;VALUE=DATE-TIME:20211122T140000Z
DTEND;VALUE=DATE-TIME:20211122T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/40
DESCRIPTION:Title: G. Kucherov\, J. O. Shallit\, J: Grytczuk\, D. Gabric\nb
y Day of short talks as part of One World Combinatorics on Words Seminar\n
\n\nAbstract\n15:00 Gregory Kucherov\, Minimizers and one question about d
e Bruijn graphs\n15:30 Jeffrey O. Shallit\, Abelian cubes and additive cub
es in the Tribonacci word\n15:45 Jarosław Grytczuk\, Twins in permutation
s\n16:15 Daniel Gabric\, Words that almost commute\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gabriele Fici
DTSTART;VALUE=DATE-TIME:20211206T140000Z
DTEND;VALUE=DATE-TIME:20211206T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/41
DESCRIPTION:Title: Some Remarks on Automatic Sequences\, Toeplitz words and Per
fect Shuffling\nby Gabriele Fici as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nOne of the many nice properties of the Thue-
Morse sequence $t = 0110100110010110\\cdots$ is that t is equal to the per
fect shuffling of itself with its binary complement $(1-t)$\, i.e.\, it ca
n be defined by means of the equation $t = t ⧢ (1 − t)$. In general\,
for any automatic sequence $w$\, there exist two automatic sequences $w'$
and $w’’$ such that $w = w' ⧢ w''$. We call the sequences $w’$ a
nd $w’’$ the even and the odd part of $w$\, respectively. We will exhi
bit some curious facts about this decomposition for some (more or less) kn
own 2- and 3-automatic sequences.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jakub Konieczny
DTSTART;VALUE=DATE-TIME:20211220T140000Z
DTEND;VALUE=DATE-TIME:20211220T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/42
DESCRIPTION:Title: Finitely-valued generalised polynomials\nby Jakub Koniec
zny as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nGen
eralised polynomials are expressions constructed from polynomials with the
use of the floor function\, addition and multiplication\, such as $\\lflo
or \\sqrt{2} n \\lfloor \\sqrt{3} n^2\\rfloor + \\sqrt{6} + \\frac{1}{2}\\
rfloor$. Despite superficial similarity\, generalised polynomials exhibit
many phenomena which are impossible for ordinary polynomials. In particula
r\, there exist generalised polynomial sequences which take only finitely
many values but are not constant. This is the case\, for instance\, for St
urmian sequences.\n\nIn my talk\, I will discuss finitely-valued generalis
ed polynomial sequences from the perspective of combinatorics on words. Th
e talk will include a survey of existing results on generalised polynomial
s\, adapted to the current context\, as well as several new results obtain
ed in joint works with Boris Adamczewski and with Jakub Byszewski.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lubomíra Dvořáková
DTSTART;VALUE=DATE-TIME:20220110T140000Z
DTEND;VALUE=DATE-TIME:20220110T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/43
DESCRIPTION:Title: On minimal critical exponent of balanced sequences\nby L
ubomíra Dvořáková as part of One World Combinatorics on Words Seminar\
n\n\nAbstract\nThe conjecture stated by Rampersad\, Shallit and Vandomme s
ays that the minimal critical exponent of balanced sequences over the alph
abet of size $d>4$ equals $(d-2)/(d-3)$. This conjecture is known to hold
for $d=5\, 6\, 7\, 8\, 9\, 10$. \n\nIn this talk\, we will describe in mor
e details the ideas and the techniques used to refute this conjecture by s
howing that the picture is different for bigger alphabets. We prove that c
ritical exponents of balanced sequences over an alphabet of size $d>10$ a
re lower bounded by $(d-1)/(d-2)$ and this bound is attained for all even
numbers $d>10$. \n\nAccording to this result\, we conjecture that the leas
t critical exponent of a balanced sequence over $d$ letters is $(d-1)/(d-2
)$ for all $d>10$.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Markus Whiteland
DTSTART;VALUE=DATE-TIME:20220124T140000Z
DTEND;VALUE=DATE-TIME:20220124T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/44
DESCRIPTION:Title: On some decidable properties of discrete-time linear dynamic
al systems\nby Markus Whiteland as part of One World Combinatorics on
Words Seminar\n\n\nAbstract\nA discrete-time linear dynamical system (LDS)
$(A\,x)$ is the orbit of a point $x \\in \\mathbb{R}^d$ under a linear ma
p $A\\colon \\mathbb{R}^d \\to \\mathbb{R}^d$. In this talk we consider de
cision problems on LDS arising from program verification\, such as reachab
ility problems: given a LDS $(A\,x)$ and a semi-algebraic target set $T \\
in \\mathbb{R}^d$\, does the orbit intersect $T$? It is well-known that su
ch questions quickly lead to open problems\, such as Skolem's problem on l
inear recurrence sequences. We identify the borderline between hard instan
ces and decidable instances with respect to the dimension of the target se
t $T$. The methods used in the decidable cases quickly give rise to symbol
ic dynamical systems over which we have a lot of control: this allows us t
o go beyond mere reachability to deciding $\\omega$-regular properties of
the LDS with respect to a low-dimensional target set $T$.\n\nJoint work wi
th C. Baier\, F. Funke\, S. Jantsch\, T. Karimov\, E. Lefaucheux\, F. Luca
\, J. Ouaknine\, D. Purser\, A. Varonka\, and J. Worrell.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Dekking
DTSTART;VALUE=DATE-TIME:20220207T140000Z
DTEND;VALUE=DATE-TIME:20220207T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/45
DESCRIPTION:Title: Combinatorics of Fibonacci and golden mean number representa
tions\nby Michel Dekking as part of One World Combinatorics on Words S
eminar\n\n\nAbstract\nHow many ways are there to represent a number as a s
um of powers of the golden mean? Among these\, what is the best way to do
this? What is the relation with representing a number as a sum of Fibonacc
i numbers?\n\nI will give some answers to these questions in my talk.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean-Paul Allouche
DTSTART;VALUE=DATE-TIME:20220307T140000Z
DTEND;VALUE=DATE-TIME:20220307T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/46
DESCRIPTION:Title: Thue and 7-3\nby Jean-Paul Allouche as part of One World
Combinatorics on Words Seminar\n\n\nAbstract\nMarch 7\, 2022 (in French 7
/3) is the 100th anniversary of the death of Axel Thue. He was a Norwegian
mathematician\, principally known for his work in Diophantine approximati
on\, but he is also known for his work in combinatorics.\n\nWe will speak
a little of his number-theoretic papers\, and more about his contribution
in combinatorics\, essentially restricting ourselves to the –ubiquitous
– Thue-Morse or Prouhet-Thue-Morse sequence. We will try to survey not o
nly some well-known features of this sequence\, but also less classical pr
operties: one of these is an occurrence of… 7/3 for this sequence\, the
other is about Shogi (将棋)\, or Japanese chess\, and the Sennichite (
千日手) (a new rule decided after a play dated March… 8\, 1983).\n\nT
o conclude this abstract\, we do not resist to give a quote of Thue: “Th
e further removed from usefulness or practical application\, the more impo
rtant.” Removed from practical application? one might want to look at th
e definition of the programming language “Thue” that Wikipedia describ
es as follows: “Thue is an esoteric programming language invented by Joh
n Colagioia in early 2000. It is a meta-language that can be used to defin
e or recognize Type-0 languages from the Chomsky hierarchy. Because it is
able to define languages of such complexity\, it is also Turing-complete i
tself. Thue is based on a nondeterministic string rewriting system called
semi-Thue grammar\, which itself is named after the Norwegian mathematicia
n Axel Thue.”\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Narad Rampersad
DTSTART;VALUE=DATE-TIME:20220321T130000Z
DTEND;VALUE=DATE-TIME:20220321T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/47
DESCRIPTION:Title: Applications of Walnut to problems of local periodicity\
nby Narad Rampersad as part of One World Combinatorics on Words Seminar\n\
n\nAbstract\nThere are a number of natural choices for measuring the local
\nperiodicity at a given position $i$ of an infinite word: for instance\,\
none could consider repetitions 1) ending at position $i$\; 2) starting\na
t position $i$\; or 3) centered at position $i$. With regards to\noption
1)\, it is known that aperiodic infinite words cannot have all\nsufficient
ly large prefixes end with cubes. It is natural then to ask\nfor such wor
ds how many prefixes can end with cubes. Using Walnut\, we\nobtain a char
acterization of these prefixes for the Fibonacci word.\nRegarding option 3
)\, Mignosi and Restivo introduced an interesting\ncomplexity measure: $h_
{\\bf w}(n)$\, which is the average of the local\nperiods over the first $
n$ positions of ${\\bf w}$. Again using\nWalnut\, we estimate the asympto
tic behaviour of this function for some\n2-automatic sequences\, such as t
he Thue-Morse sequence\, the\nRudin-Shapiro sequence\, and the period-doub
ling sequence.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Etienne Moutot
DTSTART;VALUE=DATE-TIME:20220221T140000Z
DTEND;VALUE=DATE-TIME:20220221T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/48
DESCRIPTION:Title: Pattern complexity of 2D substitutive shifts\nby Etienne
Moutot as part of One World Combinatorics on Words Seminar\n\n\nAbstract\
nIn this presentation\, I will talk about pattern complexity of two-dimens
ional substitutive shifts. More precisely\, I will focus on lower bounds o
n the complexity of {\\bf aperiodic} 2D substitutive shifts.\n\n{\\it Patt
ern complexity} consists in counting the number of different mxn rectangul
ar patterns that appear in an infinite coloring of $\\mathbb Z^2$ or in a
shift space. A corollary of our recent work with Jarkko Kari on Nivat's co
njecture [1] shows that any aperiodic subshift have pattern complexity at
least $mn+1$ for all $m$ and $n$.\n\nWith Coline Petit-Jean we have been t
rying to improve this lower bound for a particular class of shift spaces:
substitutive shifts. For some substitutions ({\\it primitive} and {\\it ma
rked} substitutions)\, we show that if their shift space is aperiodic\, th
en it has complexity at least $C*mn$\, with $C>1$ a constant depending on
the substitution. I will also talk briefly about non-marked substitutions
and why our current proof does not apply to them\, even if we believe that
a similar result might still hold.\n\n[1] Decidability and Periodicity of
Low Complexity Tilings. Jarkko Kari\, Etienne Moutot\, Theory of Computin
g Systems\, 2021\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Moussa Barro
DTSTART;VALUE=DATE-TIME:20220516T130000Z
DTEND;VALUE=DATE-TIME:20220516T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/49
DESCRIPTION:Title: Billard dans le cube\nby Moussa Barro as part of One Wor
ld Combinatorics on Words Seminar\n\n\nAbstract\nOn considère le billard
dans un cube. On code une trajectoire par les faces rencontrées. Le but d
e l'exposé sera de décrire le langage d'un tel mot dans le cas ou l'orbi
te n'est pas dense.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Colin Defant
DTSTART;VALUE=DATE-TIME:20220404T130000Z
DTEND;VALUE=DATE-TIME:20220404T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/50
DESCRIPTION:Title: Anti-powers in Aperiodic Recurrent Words\nby Colin Defan
t as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nIn 20
16\, Fici\, Restivo\, Silva\, and Zamboni introduced the notion of a $k$-a
nti-power\, which is a word of the form $w_1 \\cdots w_k$\, where $w_1\,\\
ldots\,w_k$ are words of the same length that are all distinct. I will beg
in by reviewing the main results that these authors proved about anti-powe
rs. I will then discuss anti-powers appearing as factors in the Thue-Morse
word. This will lead into a discussion of anti-powers in aperiodic recurr
ent words and aperiodic morphic words.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christophe Reutenauer
DTSTART;VALUE=DATE-TIME:20220425T130000Z
DTEND;VALUE=DATE-TIME:20220425T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/51
DESCRIPTION:Title: Constructions and parametrization of conjugates of Christoff
el words\nby Christophe Reutenauer as part of One World Combinatorics
on Words Seminar\n\n\nAbstract\nFollowing a recent work of Michel Laurent
and the first author\, we propose a deformation of the Rauzy rules (equiva
lently of the de Luca construction of standard words) in order to construc
t all conjugates of all Christoffel words (equivalently of all standard wo
rds). This construction is based on integer legal Ostrowski representation
s\, following Frid. The constructed word depends only the represented inte
ger (and even works in the free group\, up to conjugation however). Choosi
ng greedy representations\, we determine of the longest border of conjugat
es\, thereby recovering results of Lapointe on the smallest periods. Choos
ing the lazy representation\, we may revisit the Sturmian graph of Epifani
o\, Frougny\, Gabriele\, Mignosi and Shallit\; in particular we show that
this graph is essentially a subgraph of the Stern-Brocot tree\, and that t
he compact graph (which is a compaction of the minimal automaton of the se
t of suffixes of a central word) is similarly embedded in the tree of cent
ral words of Aldo de Luca.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre-Adrien Tahay
DTSTART;VALUE=DATE-TIME:20220530T130000Z
DTEND;VALUE=DATE-TIME:20220530T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/52
DESCRIPTION:Title: Column representation of words in cellular automata\nby
Pierre-Adrien Tahay as part of One World Combinatorics on Words Seminar\n\
n\nAbstract\nThe task of representing a sequence over a finite alphabet in
the space-time\ndiagram of a cellular automaton is a non-trivial and stil
l not entirely explored\ntopic. One of the first results on the subject wa
s done by Fischer in 1965 with a construction of the characteristic sequen
ce of primes numbers. Many results and improvements have been established
since. In 2015\, Rowland and Yassawi showed that there is a close connecti
on between the $p$-automatic sequences and the linear cellular automata. M
ore precisly the columns of linear cellular automata are $p$-\nautomatic s
equences and all $p$-automatic sequences can be realized by some linear ce
llular automata with memory. Moreover their proof is constructive. In 2018
\, Marcovici\, Stoll and Tahay investigated some constructions for nonauto
matic sequences such as the characteristic sequences of polynomials and th
e Fibonacci word.\n\nIn this talk I will present recent results obtained i
n collaboration with Francesco Dolce where we generalized the construction
for the Fibonacci word in a column of a cellular automaton\, to any Sturm
ian word with quadratic slope. Our proof is constructive and use the ultim
ate periodicity of the continued fraction expansion of the slope of the wo
rd.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kristina Ago and Bojan Bašić
DTSTART;VALUE=DATE-TIME:20220613T130000Z
DTEND;VALUE=DATE-TIME:20220613T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/53
DESCRIPTION:Title: Some recent results on two "palindromicity" measures\nby
Kristina Ago and Bojan Bašić as part of One World Combinatorics on Word
s Seminar\n\n\nAbstract\nVarious measures of the degree of "palindromicity
" of a given word have been defined in the literature. In this talk we pre
sent some of our results concerning two such measures. The first one is th
e so-called \\emph{palindromic defect} (or only \\emph{defect}). Let $|\\m
athrm{Pal}(w)|$ denote the number of palindromic factors of a word $w$. Th
e palindromic defect of $w$ is defined by $|w|+1-|\\mathrm{Pal}(w)|$ (it c
an be proved that this value is always nonnegative). This definition can b
e naturally extended to infinite words. While infinite words whose defect
is zero (called \\emph{rich}) have been researched quite much\, there are
noticeably less results in the literature on infinite words of finite posi
tive defect. In the first part of the talk we introduce a construction of
an infinite family of infinite words whose defect is finite and in many ca
ses positive (with fully characterized cases when the defect is $0$)\, and
we analyze their properties. Each of those words is either periodic (whic
h is a less interesting case\, and explicitly characterized)\, or recurren
t but not uniformly recurrent. Examples of explicit constructions of such
words that are not uniformly recurrent have been quite deficient in the li
terature so far.\n\nThe second part of talk is devoted to the so-called \\
emph{MP-ratio}. The concept of MP-ratio is based on palindromic subwords (
and not factors) of a given finite word. Call a word over an $n$-ary alpha
bet \\emph{minimal-palindromic} if it does not contain palindromic subword
s of length greater than $\\big\\lceil\\frac{|w|}n\\big\\rceil$. The \\emp
h{MP-ratio} of a given $n$-ary word $w$ is defined as the quotient $\\frac
{|rws|}{|w|}$\, where $r$ and $s$ are words such that the word $rws$ is mi
nimal-palindromic and that the length $|r|+|s|$ is minimal possible. In or
der for the MP-ratio to be well-defined\, it has to be shown that such a p
air $(r\,s)$ always exist. It has been known for some time that this is tr
ue in the binary case\, but this question becomes much more complicated fo
r larger arities. In this talk we show that the MP-ratio is well-defined f
or any arity\, and we present some further results on this topic.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Antoine Domenech
DTSTART;VALUE=DATE-TIME:20220620T130000Z
DTEND;VALUE=DATE-TIME:20220620T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/54
DESCRIPTION:Title: Avoiding doubled patterns\nby Antoine Domenech as part o
f One World Combinatorics on Words Seminar\n\n\nAbstract\nA pattern $P$ is
$k$-avoidable if there exists\nan infinite word over $k$ letters that con
tains no occurrence of $P$.\nA pattern is doubled if all its variables app
ear at least twice.\nIt is known that doubled patterns are 3-avoidable and
it is conjectured\nthat only a finite number of doubled patterns are not
2-avoidable.\nWe show that square-free doubled patterns with at most 4 var
iables are 2-avoidable.\nThen\, for each pattern doubled $P$ with at most
3 variables that is\nnot 2-avoidable\, we determine the minimum number of
distinct\noccurrences of $P$ that are contained in an infinite binary word
.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre Popoli
DTSTART;VALUE=DATE-TIME:20220627T130000Z
DTEND;VALUE=DATE-TIME:20220627T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/55
DESCRIPTION:Title: Maximum order complexity for some automatic and morphic sequ
ences along polynomial values\nby Pierre Popoli as part of One World C
ombinatorics on Words Seminar\n\n\nAbstract\nAutomatic sequences are not s
uitable sequences for cryptographic\napplications since both their subword
complexity and their expansion\ncomplexity are small\, and their correlat
ion measure of order 2 is\nlarge. These sequences are highly predictable d
espite having a large\nmaximum order complexity. However\, recent results
show that polynomial\nsubsequences of automatic sequences\, such as the Th
ue-Morse sequence\nor the Rudin-Shapiro sequence\, are better candidates f
or pseudorandom\nsequences. A natural generalization of automatic sequence
s are morphic\nsequences\, given by a fixed point of a prolongeable morphi
sm that is\nnot necessarily uniform. In this talk\, I will present my resu
lts on\nlowers bounds for the maximum order complexity of the Thue-Morse\n
sequence\, the Rudin-Shapiro sequence and the sum of digits function in\nZ
eckendorf base\, which are respectively automatics and morphic\nsequences.
\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zachary Chase
DTSTART;VALUE=DATE-TIME:20220711T130000Z
DTEND;VALUE=DATE-TIME:20220711T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/56
DESCRIPTION:Title: The separating words\, $k$-deck\, and trace reconstruction p
roblems\nby Zachary Chase as part of One World Combinatorics on Words
Seminar\n\n\nAbstract\nWhat is the smallest size of a DFA that can separat
e two\ngiven strings of length $n$? Can two distinct strings of length $n$
have\nthe same multiset of subsequences of length $n^{1/3}$? How many ran
dom\nsubsequences of length $n/2$ of an unknown string $x$ of length $n$ d
o you\nneed to determine $x$ with high probability? We discuss these three
\nproblems\, each having an exponential gap between the best known upper\n
and lower bounds\, and touch upon how they might be more related than\none
might expect.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shuo Li
DTSTART;VALUE=DATE-TIME:20220919T130000Z
DTEND;VALUE=DATE-TIME:20220919T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/57
DESCRIPTION:Title: On the number of squares in a finite word\nby Shuo Li as
part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA conject
ure of Fraenkel and Simpson states that the number of distinct squares in
a finite word $w$\n is bounded by its length. In this talk\, we will revie
w this conjecture from the perspective of the topological properties of th
e Rauzy graphs of $w$. We prove this conjecture by giving a stronger state
ment: the number of distinct squares in a finite word \n$w$ is bounded by
the length of $w$ minus the number of distinct letters in $w$.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/57/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robbert Fokkink
DTSTART;VALUE=DATE-TIME:20221003T130000Z
DTEND;VALUE=DATE-TIME:20221003T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/58
DESCRIPTION:Title: A few words on games\nby Robbert Fokkink as part of One
World Combinatorics on Words Seminar\n\n\nAbstract\nAn impartial combinato
rial game involves a set of positions that are either won or lost for the
player that moves next. These are the so-called N-positions. If you know t
he set of N-positions\, then you have solved the game. Members of our comm
unity will immediately wonder if the characteristic sequence of the set of
N-positions form a word. It turns out that Fibonacci word gives the set o
f N-positions in Wythoff Nim. Eric Duchene and Michel Rigo found other exa
mples of impartial games that are given by words\, initiating ongoing work
on the link between words and games. In this talk I will show how a modif
ication of Wythoff Nim can be described by the Tribonacci word. This is jo
int work with Dan Rust and Cisco Ortega.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/58/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Giuseppe Romana
DTSTART;VALUE=DATE-TIME:20221017T130000Z
DTEND;VALUE=DATE-TIME:20221017T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/59
DESCRIPTION:Title: String Attractor: a Combinatorial object from Data Compressi
on\nby Giuseppe Romana as part of One World Combinatorics on Words Sem
inar\n\n\nAbstract\nVery recently\, Kempa and Prezza [STOC 2018] introduce
d the notion of String Attractor in the field of Data Compression\, and sh
owed how this concept was already implicit in many other well known compre
ssion schemes.\nBasically\, a String Attractor $\\Gamma$ of a finite word
$w$ is a set of positions in $w$ such that each distinct factors that occu
rs in $w$ has at least an occurrence that crosses a position $j \\in \\Gam
ma$. \nIn this talk\, we explore String Attractors from a combinatorial pe
rspective.\nWe discuss how the size $\\gamma^*$ of a string attractor of m
inimum size is affected when some classical combinatorial operations are a
pplied to finite words.\nFurther\, we show how the size and other structur
al properties of string attractors can be used to obtain new characterizat
ions for infinite words.\nMost of the results presented in this talk come
from [A combinatorial view on string attractors\, Theoret. Comput. Sci. 20
21] and [String Attractors and Infinite Words\, LATIN 2022] (to appear).\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/59/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Krenn
DTSTART;VALUE=DATE-TIME:20221107T140000Z
DTEND;VALUE=DATE-TIME:20221107T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/60
DESCRIPTION:Title: $q$-Recursive Sequences and their Asymptotic Analysis\nb
y Daniel Krenn as part of One World Combinatorics on Words Seminar\n\n\nAb
stract\nIn this talk\, we consider Stern’s diatomic sequence\, the numbe
r of\nnon-zero elements in some generalized Pascal's triangle and the numb
er\nof unbordered factors in the Thue-Morse sequence as running examples.\
nAll these sequences can be defined recursively and lead to the concept\no
f so-called $q$-recursive sequences. Here $q$ is an integer and at least $
2$\,\nand $q$-recursive sequences are sequences which satisfy a specific t
ype of\nrecurrence relation: Roughly speaking\, every subsequence whose in
dices\nrun through a residue class modulo $q^M$ is a linear combination of
\nsubsequences where for each of these subsequences\, the indices run\nthr
ough a residue class modulo $q^m$ for some $m < M$.\n\nIt turns out that t
his property is quite natural and many combinatorial\nsequences are in fac
t $q$-recursive. We will see that $q$-recursive\nsequences are related to
$q$-regular sequences and a $q$-linear\nrepresentation of a sequence can b
e computed easily. Our main focus is the asymptotic\nbehavior of the summa
tory functions of $q$-recursive sequences. Beside\ngeneral results\, we pr
esent a precise asymptotic analysis of our three examples. For the first t
wo sequences\, our analysis even leads to\nprecise formulae without error
terms.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/60/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sebastián Barbieri
DTSTART;VALUE=DATE-TIME:20221121T140000Z
DTEND;VALUE=DATE-TIME:20221121T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/61
DESCRIPTION:Title: Indistinguishable asymptotic pairs\nby Sebastián Barbie
ri as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nWe s
ay two bi-infinite words are asymptotic if they differ in finitely many co
ordinates. We say they are indistinguishable if for any finite word w\, th
e number of occurrences of w that intersect the set of differences in each
of them is the same. In this talk we will study these objects and show th
at they are very closely related to Sturmian configurations. We will also
show that a higher-dimensional analogue of the theorem holds\, and as an a
pplication of this result we will provide a formula for computing the comp
lexity of a multidimensional Sturmian configuration on any finite connecte
d support. This is joint work with S. Labbé.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/61/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Josef Rukavicka
DTSTART;VALUE=DATE-TIME:20221205T140000Z
DTEND;VALUE=DATE-TIME:20221205T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/62
DESCRIPTION:Title: Palindromic factorization of rich words\nby Josef Rukavi
cka as part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA f
inite word $w$ is called rich if it contains $\\vert w\\vert+1$ distinct p
alindromic factors including the empty word. For every finite rich word $w
$ there are distinct nonempty palindromes $w_1\, w_2\,\\dots\,w_p$ such th
at $w=w_pw_{p-1}\\cdots w_1$ and $w_i$ is the longest palindromic suffix o
f $w_pw_{p-1}\\cdots w_i$\, where $1\\leq i\\leq p$. This palindromic fact
orization is called UPS-factorization. Let $luf(w)=p$ be the length of UPS
-factorization of $w$.\n\nIn 2017\, it was proved that there is a constant
$c$ such that if $w$ is a finite rich word and $n=\\vert w\\vert$ then $l
uf(w)\\leq c\\frac{n}{\\ln{n}}$.\nWe improve this result as follows: There
are constants $\\mu\, \\pi$ such that if $w$ is a finite rich word and $n
=\\vert w\\vert$ then \\[luf(w)\\leq \\mu\\frac{n}{e^{\\pi\\sqrt{\\ln{n}}}
}\\mbox{.}\\]\nThe constants $c\,\\mu\,\\pi$ depend on the size of the alp
habet.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/62/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jason Bell
DTSTART;VALUE=DATE-TIME:20221219T140000Z
DTEND;VALUE=DATE-TIME:20221219T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/63
DESCRIPTION:Title: Noncommutative rational Pólya series\nby Jason Bell as
part of One World Combinatorics on Words Seminar\n\n\nAbstract\nA Pólya s
eries over a field $K$ is a formal noncommutative power series whose nonze
ro coefficients are contained in a finitely generated subgroup of the mult
iplicative group of $K$. A complete description of such one-variable serie
s was given by Pólya\, and an extension to general noncommutative rationa
l series in terms of unambiguous weight automaton was later conjectured by
Reutenauer. We explain how to prove Reutenauer’s conjecture and discus
s certain decidability aspects of our work. This is joint work with Danie
l Smertnig.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/63/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pamela Fleischmann
DTSTART;VALUE=DATE-TIME:20230109T140000Z
DTEND;VALUE=DATE-TIME:20230109T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/64
DESCRIPTION:by Pamela Fleischmann as part of One World Combinatorics on Wo
rds Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/64/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Natalie Behague
DTSTART;VALUE=DATE-TIME:20221024T130000Z
DTEND;VALUE=DATE-TIME:20221024T140000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/65
DESCRIPTION:Title: Synchronizing Times for $k$-sets in Automata\nby Natalie
Behague as part of One World Combinatorics on Words Seminar\n\n\nAbstract
\nAn automaton consists of a finite set of states and a collection of func
tions from the set of states to itself. An automaton is synchronizing if t
here is a word (that is\, a sequence of functions) that maps all states on
to the same state. Černý’s conjecture on the length of the shortest su
ch word is one of the most famous open problem in automata theory. We cons
idered the closely related question of determining the minimum length of a
word that maps some k states onto a single state.\n\nFor synchronizing au
tomata\, we found a simple argument for general k almost halving the upper
bound on the minimum length of a word sending k states to a single state.
We further improved the upper bound on the minimum length of a word sendi
ng 4 states to a singleton from $0.5n^2$ to $≈ 0.459n^2$\, and the minim
um length sending 5 states to a singleton from $n^2$ to $≈ 0.798n^2$. I
will discuss this result and some open questions.\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/65/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lubomíra Dvořáková
DTSTART;VALUE=DATE-TIME:20230123T140000Z
DTEND;VALUE=DATE-TIME:20230123T150000Z
DTSTAMP;VALUE=DATE-TIME:20221209T225602Z
UID:CombinatoricsOnWords/66
DESCRIPTION:by Lubomíra Dvořáková as part of One World Combinatorics o
n Words Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CombinatoricsOnWords/66/
END:VEVENT
END:VCALENDAR