Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
shorttalksfebruary2021 [2022/10/30 23:04] – old revision restored (2021/01/25 16:12) 139.124.146.3shorttalksfebruary2021 [2022/10/30 23:04] (current) – old revision restored (2020/12/09 12:11) 139.124.146.3
Line 1: Line 1:
-======  Day of Short Talks on Combinatorics on Words, February 22, 2021 ======+======  Day of Short Talks on Combinatorics on Words ======
  
 This mini-event, organized by [[start|One World Combinatorics on Words Seminar]], is designed to take the place of a small and very informal conference in our field, since many of us miss direct communication of this kind. This mini-event, organized by [[start|One World Combinatorics on Words Seminar]], is designed to take the place of a small and very informal conference in our field, since many of us miss direct communication of this kind.
Line 10: Line 10:
  
 ==== Interested speakers ==== ==== Interested speakers ====
- 
-** Ibai Aedo ** //On long arithmetic progressions in binary Morse-like words// 
- 
-In this talk, I will present a joint work with Uwe Grimm, Yasushi Nagai and Petra Staynova based on a recent preprint: arXiv:2101.02056. Regarding the Prouhet-Thue-Morse word as a two-colouring of the positive integers, we look for long monochromatic arithmetic progressions occurring in the sequence. 
- 
-The size of the longest arithmetic progression of difference $d=2^n-1$ was previously established by O. Parshina. Using a different approach, mainly based on exploiting the substitution structure of the Prouhet-Thue-Morse word, we will show how we can re-establish this result and find another series of long arithmetic progressions of difference d=2^n+1. Then, we will comment on a generalisation of these results for a special class of bijective binary words, and we will finish with some more general results and some open questions. 
- 
  
 ** Mélodie Andrieu** //A Rauzy fractal unbounded in all directions of the plane// ** Mélodie Andrieu** //A Rauzy fractal unbounded in all directions of the plane//
Line 24: Line 17:
 The study of the pairs of abelianized factors of Arnoux-Rauzy words disproves this belief. The study of the pairs of abelianized factors of Arnoux-Rauzy words disproves this belief.
  
-**Célia Cisternino** //Two applications of the composition of a $2$-tape automaton and a weighted automaton// +** Anna Frid** //The semigroup of trimmed morphisms//
- +
-Starting with a $2$-tape automaton ${\mathcal A}$ and a weighted automaton ${\mathcal B}$, we can obtain a new $K$-automaton using an ad hoc operation that can be considered as the composition ${\mathcal B}\circ {\mathcal A}$. First, I will define and illustrate this operation. Next, I will present an application of this operation on automata in terms of synchronized relation and formal series. In particular, using the characterization of synchronized sequences in terms of synchronized relations and that of regular sequences in terms of formal series, I will present two consequences of this composition of automata in the theory of regular sequences.  +
- +
-This is a joint work with Émilie Charlier and Manon Stipulanti based on two recent papers: [[https://arxiv.org/abs/2012.04969|arXiv:2012.04969]] and [[https://arxiv.org/abs/2006.11126|arXiv:2006.11126]]. +
- +
-**Francesco Dolce** //On morphisms preserving palindromic richness// +
- +
-A finite word is said to be rich if it has maximal number of palindromic factors (this is known to be the length of the word plus one). This definition can be naturally extended to infinite words.Sturmian words and Rote complementary symmetric sequences form two classes of binary rich words, while strict episturmian words and words coding symmetric interval exchange transformations give us other examples on larger alphabets. +
-In this talk we study homomorphisms of the free monoid which allow to construct new rich words from already known rich words. In particular, we focus on two types of morphisms: Arnoux-Rauzy morphisms and morphisms from Class $P_{ret}$. These morphisms contain Sturmian morphisms as a subclass. We show that Arnoux-Rauzy morphisms preserve the set of all rich words. +
-We also characterize $P_{ret}$ morphisms which preserve richness on binary alphabet. +
-This is a joint work with Edita Pelantová. +
- +
-**Lubka Dvořáková** //On balanced sequences with the minimal asymptotic critical exponent// +
- +
-We study balanced sequences over a $d$-letter alphabet, $d\geq 3$.  Any balanced sequence is defined by a Sturmian sequence and two periodic constant gap sequences $y$ and $y‘$. The minimal value $E(d)$ of the critical exponent of balanced sequences over a $d$-letter alphabet has been recently determined by Baranwal, Rampersad, Shallit, and Vandomme for $d\leq 8$. We focus on the minimal asymptotic critical exponent $E^*(d)$. We show that $E(d)$ and $E^*(d)$ coincide if $d\leq 5$ and differ if $6\leq d\leq 8$. We determine $E^*(6) $ and give an upper bound on $E^*(d)$, $d\leq 15$. +
- +
-Our method is based on the construction of a finite directed labeled graph $\Gamma$ which depends on the period lengths of $y$ and $y'$ and on a parameter $\beta>1$. The graph has the following property: If $\Gamma$ does not contain an oriented cycle, then any balanced sequence arising by $y$ and $y‘$ has the asymptotic critical exponent at least $\beta$. +
-On the other hand, if $\Gamma$ contains an oriented cycle labeled by $p$, then we inspect all balanced sequences associated to Sturmian sequences whose slopes have the continued fraction expansion with the period  $p$.  The program we have implemented finds among them the balanced sequence with the minimal asymptotic critical exponent.   +
- +
-This is a joint work with Edita Pelantová.+
  
 ** Štěpán Holub** //Formalization of Combinatorics on Words in Isabelle/HOL// ** Štěpán Holub** //Formalization of Combinatorics on Words in Isabelle/HOL//
Line 56: Line 29:
  
 To achieve these results, we introduce a novel data-structure, called Simon-Tree, which allows us to construct a natural representation of the equivalence classes induced by $\sim_k$ on the set of suffixes of a word, for all $k\geq 1$. We show that such a tree can be constructed for an input word in linear time. Then, when working with two words $s$ and $t$, we compute their respective Simon-Trees and efficiently build a correspondence between the nodes of these trees. This correspondence, which can also be constructed in linear time $O(|s|+|t|)$, allows us to retrieve the largest $k$ for which $s\sim_k t$. To achieve these results, we introduce a novel data-structure, called Simon-Tree, which allows us to construct a natural representation of the equivalence classes induced by $\sim_k$ on the set of suffixes of a word, for all $k\geq 1$. We show that such a tree can be constructed for an input word in linear time. Then, when working with two words $s$ and $t$, we compute their respective Simon-Trees and efficiently build a correspondence between the nodes of these trees. This correspondence, which can also be constructed in linear time $O(|s|+|t|)$, allows us to retrieve the largest $k$ for which $s\sim_k t$.
- 
-**Jane D. Palacio** //Coverable bi-infinite substitution shifts// 
- 
-A finite or infinite word $w$ is said to be coverable if it can be formed by 
-overlapping or adjacent occurrences of some finite subword $u$ of $w$. Coverability of finite words was introduced by A. Apostolico and A. Ehrenfeucht in the  
-context of text algorithms in 1993. In 2004, S. Marcus extended the concept 
-of coverability to (one-sided) infinite sequences. In this presentation, we will 
-define the notion of coverable bi-infinite shifts. 
- 
-In general, coverability of subshifts is not topologically invariant. Nevertheless, we show that a special type of coverability of substitutive shifts is invariant under topological conjugacy. To better understand coverability of 
-bi-infinite shifts, we aim to identify properties of substitutions that ensure 
-coverability or non-coverability of its associated shifts. 
- 
-This is joint work with Manuel Joseph Loquias and Eden Delight Miro. 
- 
- 
-** Christophe Reutenauer ** //An arithmetical characterization of Christoffel words// 
- 
-Christoffel word have many combinatorial characterizations. 
-I propose a new one, of arithmetical nature: a primitive word on the alphabet $11$, $22$ is a Christoffel word if and only if for any of its conjugates, $u=a_1\cdots a_{2n}$ say, one has 
-$p(a_1,\ldots,a_{2n}) - p(a_2,\ldots,a_{2n-1}) < 3 p(a_2,\ldots,a_{2n})$. 
- 
-Here $p(x_1,\ldots,x_k)$ denotes the continuant polynomials, defined recursively by $p()=1$, $p(x_1)=x_1$, and 
-$p(x_1,\ldots,x_k)=x_1p(x_2,\ldots,x_k)+p(x_3,\ldots,x_k)$. 
- 
-These polynomials are well-known in the theory of continued fractions. One has for example $p(x,y)=xy+1$, $p(x,y,z)=xyz+x+z$, $p(x,y,z,t)=xyzt+xy+xt+zt+1$. 
- 
-The characterization above is motivated by the theory of Markoff. As intermediate result, I prove another characterization: 
-a primitive word $w$ on the alphabet $\{a<b\}$ is a Christoffel word if and only for any conjugate $aub$ (resp. $bua$) of $w$, one has $u \geq_{lex} \tilde u$ (resp. $u \leq_{lex} \tilde u$). This condition must be called the finitary Markoff condition, due to its similarity to Markoff’s condition on bi-infinite words, which appears in his articles of 1880. 
- 
- 
  
 ** Jeffrey  Shallit** //Robbins and Ardila meet Berstel// ** Jeffrey  Shallit** //Robbins and Ardila meet Berstel//