Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| shorttalksjune2021 [2022/10/30 22:44] – old revision restored (2021/04/19 15:38) 139.124.146.3 | shorttalksjune2021 [2022/10/30 22:44] (current) – old revision restored (2021/04/19 10:32) 139.124.146.3 |
|---|
| |
| 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. | |