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
shorttalksjune2021 [2022/10/30 21:44] – old revision restored (2021/04/24 10:59) 139.124.146.3shorttalksjune2021 [2022/10/30 21:44] (current) – old revision restored (2021/04/19 10:32) 139.124.146.3
Line 4: Line 4:
  
 As usual, the event will consist of short talks in 25-minute slots, including your new results, discussions, and open questions. This time, researchers from other fields who use combinatorics on words are especially welcome. As usual, the event will consist of short talks in 25-minute slots, including your new results, discussions, and open questions. This time, researchers from other fields who use combinatorics on words are especially welcome.
 +
 +If you want to give a talk, please write a message to Anna Frid.
  
 ==== Speakers ==== ==== Speakers ====
Line 11: Line 13:
  
 In Fibonacci coding we forbid '11' patterns, bringing question of generalization to more complex constraints. I will very briefly present how to practically handle such general situation, including 2D lattice (hard square problem), with motivation e.g. to increase capacity of hard disk. We will first find probability distribution of patterns in such ensemble of sequences, which can be obtained with MERW ( https://en.wikipedia.org/wiki/Maximal_entropy_random_walk ). Then we can use entropy coder - for this purpose I have introduced ANS ( https://en.wikipedia.org/wiki/Asymmetric_numeral_systems ): generalization of numeral systems to optimize for a chosen probability distribution of digits. I will also briefly present its two widely used variants: rANS with multiplication - now e.g. in JPEG XL image format, or tANS building finite state automaton for a given probability distribution - now used e.g. in Facebook Zstandard or Apple LZFSE compressors. In Fibonacci coding we forbid '11' patterns, bringing question of generalization to more complex constraints. I will very briefly present how to practically handle such general situation, including 2D lattice (hard square problem), with motivation e.g. to increase capacity of hard disk. We will first find probability distribution of patterns in such ensemble of sequences, which can be obtained with MERW ( https://en.wikipedia.org/wiki/Maximal_entropy_random_walk ). Then we can use entropy coder - for this purpose I have introduced ANS ( https://en.wikipedia.org/wiki/Asymmetric_numeral_systems ): generalization of numeral systems to optimize for a chosen probability distribution of digits. I will also briefly present its two widely used variants: rANS with multiplication - now e.g. in JPEG XL image format, or tANS building finite state automaton for a given probability distribution - now used e.g. in Facebook Zstandard or Apple LZFSE compressors.
- 
-** [[https://www.researchgate.net/profile/Palak-Pandoh|Palak Pandoh]]** //Counting scattered palindromes in a finite word// 
- 
-We investigate the scattered palindromic subwords in a finite word. We start by characterizing the words with the least number of scattered palindromic subwords. Then, we give an upper bound for the total number of palindromic subwords in a word of length $n$ in terms of Fibonacci number $F_n$ and prove that at most $F_n$ new scattered palindromic subwords can be created on the concatenation of a letter to a word of length $n − 1$. We then show that the maximum number of scattered palindromic subwords in a word depends both on the length of the word and the number of distinct letters in the word. We finally give a tight bound on the number of scattered palindromic subwords in a word of length $n$ that has at least $n/2$ distinct letters. 
- 
-** [[https://www.researchgate.net/profile/Bartlomiej-Pawlik|Bartłomiej Pawlik]]  ** //Nonchalant procedure// 
- 
-Recently, [[https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p48|Gryczuk, Kordulewski and Niewiadomski]] introduced the concept of the nonchalant procedure. In the original form, the procedure generates square-free words over the alphabet $\{1,2,3\}$ in such manner that every word (except for the initial word "$1$") is the extension of the preceding word by inserting the first letter possible (in the natural order on respective alphabet) before the shortest suffix possible (preferably of the length $0$) resulting in the new word being square-free.  Aforementioned article contains the conjecture, that such a procedure never stops. 
- 
-While the conjecture remains open, further investigation of the subject pointed out certain "flexibility" of the nonchalant procedure - it can be considered in various contextes, not necessarily focused on combinatorics on words.  In this talk we will present and analyze a few variants of the procedure. 
- 
-** [[https://www.utu.fi/en/people/jarkko-peltomaki|Jarkko Peltomäki]] ** //Initial nonrepetitive complexity of regular episturmian words and their Diophantine exponents// 
- 
-Regular episturmian words are episturmian words whose 
-directive words $x_1^{a_1} x_2^{a_2} \dotsm$ have the property that $x_1 
-x_2 \dotsm = u^\omega$ for a word $u$ whose all letters are distinct. 
-This subclass of episturmian words contains all Sturmian words and 
-generalizations of the Fibonacci word. 
- 
-The Diophantine exponent $\mathrm{dio}(x)$ of an infinite word $x$ is 
-the supremum $\rho$ of real numbers for which there exist arbitrarily 
-long prefixes of $x$ of the form $UV^e$ such that $|UV^e|/|UV| \geq 
-\rho$. This concept is especially interesting since $\mathrm{dio}(x)$ 
-gives a lower bound for the irrationality exponent of the real number 
-having $x$ as a fractional part. 
- 
-In the talk, I will discuss how the Diophantine exponent of an infinite 
-word can be found by studying its initial nonrepetitive complexity 
-function. Then I will explain how to determine the initial nonrepetitive 
-complexity of regular episturmian words and describe what can then be 
-inferred of their Diophantine exponents. The main corollaries of the 
-results are as follows. Under certain mild conditions, a real number 
-having a regular episturmian word as a fractional part has irrationality 
-exponent $> 2$. Moreover, such a number has irrationality exponent 
-$\infty$ (i.e., it is a Liouville number) if and only if the 
-corresponding directive word has unbounded partial quotients. 
- 
-** Clément Lagisquet ** ([[https://www.lama.univ-smb.fr/index.php?use=membres&equipe=Logique&lang=en|LAMA]]) //On Markov Numbers: An answer to three conjectures from Aigner// 
- 
-Markov numbers are the positive integer solutions of the Diophantine equation $x^2+y^2+z^2=3xyz$. In 1880, Markov showed that all solutions could be generated along a binary tree. Thus, it is quite natural and usual to index the Markov numbers by the rational in $[0,1]$, which has the same position in the Stern-Brocot tree. The Frobenius conjecture states that each Markov number appears one and only one time in the tree. 
- 
-If the conjecture is true, then the ordering on the Markov numbers would give a new (strict) order on the rationals. In his book Aigner suggests three conjectures in order to better understand this ordering. The first was proved last year. In this work we prove the other two using techniques based on discrete geometry and combinatorics on word. 
-We also generalize the Markov numbers to every couple $(p,q)$ in $\mathbb N^2$ (not only the relatively prime ones) and conjecture that the unicity still holds if $p<q$. Lastly, we prove that the three conjectures are still true for this superset. 
- 
-Based on the submitted paper https://arxiv.org/abs/2010.10335.