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 22:04] – old revision restored (2021/02/16 12:16) 139.124.146.3shorttalksfebruary2021 [2022/10/30 22: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.
  
-The event will consist of short talks in 25-minute slots, including your new results, discussions, and open questions.+The event will consist of short talks in 25-minute slots, including your new results, discussions, and open questions. If you are interested in giving such a talk, please send your title and abstract to Anna Frid (anna.e.frid@gmail.com) as soon as possible.
  
-The deadline for submissions was January 24, 2021+The abstracts (with eventual references to arxiv.org), slides and some videos of talks will be published at this page.
  
-==== Speakers ====+Deadline for submissions: January 24, 2021
  
-** 15:00 [[http://lacim-membre.uqam.ca/~christo/|Christophe Reutenauer]] ** //An arithmetical characterization of Christoffel words//+==== Interested speakers ====
  
-Christoffel word have many combinatorial characterizations. +** Mélodie Andrieu** //A Rauzy fractal unbounded in all directions of the plane//
-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 +Until 2001 it was believed that, as for Sturmian words, the imbalance of Arnoux-Rauzy words was bounded - or at least finite.  Cassaigne, Ferenczi and Zamboni disproved this conjecture by constructing an Arnoux-Rauzy word with infinite imbalance, i.e. a word whose broken line deviates regularly and further and further from its average direction.  
-$p(x_1,\ldots,x_k)=x_1p(x_2,\ldots,x_k)+p(x_3,\ldots,x_k)$.+Today, we hardly know anything about the geometrical and topological properties of these unbalanced Rauzy fractals. The Oseledets theorem suggests that these fractals are contained in a strip of the plane: indeed, if the Lyapunov exponents of the matricial product associated with the word exist, one of these exponents at least is nonpositive since their sum equals zero. 
 +The study of the pairs of abelianized factors of Arnoux-Rauzy words disproves this belief.
  
-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$.+** Anna Frid** //The semigroup of trimmed morphisms//
  
-The characterization above is motivated by the theory of Markoff. As intermediate result, I prove another characterization: +** Štěpán Holub** //Formalization of Combinatorics on Words in Isabelle/HOL//
-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. +
- +
- +
- +
-** 15:30 [[https://www.uliege.be/cms/c_9054334/fr/repertoire?uid=u227158|Célia Cisternino]]** //Two applications of the composition of a $2$-tape automaton and a weighted automaton// +
- +
-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]]. +
- +
- +
-** 16:00 [[https://kmlinux.fjfi.cvut.cz/~balkolub/|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á. +
- +
-** 16:30 [[https://www2.karlin.mff.cuni.cz/~holub/|Štěpán Holub]]** //Formalization of Combinatorics on Words in Isabelle/HOL//+
  
 We present an ongoing project of formalization of Combinatorics on Words We present an ongoing project of formalization of Combinatorics on Words
 in the proof assistant Isabelle/HOL. in the proof assistant Isabelle/HOL.
  
-** 17:00 [[http://flmanea.blogspot.com/|Florin Manea]]** //Efficiently Testing Simon's Congruence// [[https://arxiv.org/abs/2005.01112|full text]]+** Florin Manea** //Efficiently Testing Simon's Congruence// [[https://arxiv.org/abs/2005.01112|full text]]
  
 Simon's congruence $\sim_k$ is a relation on words defined by Imre Simon in the 1970s and intensely studied since then. This congruence was initially used in connection to piecewise testable languages, but also found many applications in, e.g., learning theory, databases theory, or linguistics. The $\sim_k$-relation is defined as follows: two words are $\sim_k$-congruent if they have the same set of subsequences of length at most $k$. A long standing open problem, stated already by Simon in his initial works on this topic, was to design an algorithm which computes, given two words $s$ and $t$, the largest $k$ for which $s\sim_k t$. We propose the first algorithm solving this problem in linear time $O(|s|+|t|)$ when the input words are over the integer alphabet $\{1,\ldots,|s|+|t|\}$ (or other alphabets which can be sorted in linear time). Our approach can be extended to an optimal algorithm in the case of general alphabets as well. Simon's congruence $\sim_k$ is a relation on words defined by Imre Simon in the 1970s and intensely studied since then. This congruence was initially used in connection to piecewise testable languages, but also found many applications in, e.g., learning theory, databases theory, or linguistics. The $\sim_k$-relation is defined as follows: two words are $\sim_k$-congruent if they have the same set of subsequences of length at most $k$. A long standing open problem, stated already by Simon in his initial works on this topic, was to design an algorithm which computes, given two words $s$ and $t$, the largest $k$ for which $s\sim_k t$. We propose the first algorithm solving this problem in linear time $O(|s|+|t|)$ when the input words are over the integer alphabet $\{1,\ldots,|s|+|t|\}$ (or other alphabets which can be sorted in linear time). Our approach can be extended to an optimal algorithm in the case of general alphabets as well.
Line 52: Line 30:
 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$.
  
-** 17:30 [[http://www.i2m.univ-amu.fr/perso/andrieu-es.m/index.html|Mélodie Andrieu]]** //A Rauzy fractal unbounded in all directions of the plane// +** Jeffrey  Shallit** //Robbins and Ardila meet Berstel//
- +
-Until 2001 it was believed that, as for Sturmian words, the imbalance of Arnoux-Rauzy words was bounded - or at least finite.  Cassaigne, Ferenczi and Zamboni disproved this conjecture by constructing an Arnoux-Rauzy word with infinite imbalance, i.e. a word whose broken line deviates regularly and further and further from its average direction.  +
-Today, we hardly know anything about the geometrical and topological properties of these unbalanced Rauzy fractals. The Oseledets theorem suggests that these fractals are contained in a strip of the plane: indeed, if the Lyapunov exponents of the matricial product associated with the word exist, one of these exponents at least is nonpositive since their sum equals zero. +
-The study of the pairs of abelianized factors of Arnoux-Rauzy words disproves this belief.+
  
 +In this short talk I show how to obtain a result of Robbins and (later)
 +Ardila on partitions of integers in Fibonacci numbers, and much more,
 +using a 2001 transducer created by Jean Berstel.   The "fun" part is
 +that once you have Berstel's transducer, the rest follows by purely
 +computational means.