Combinatorical and Algebraic Structures Seminar
Session details
| Date: | 1.3.2011 |
| Speaker: | Ľubomíra Balková, FJFI, České vysoké učení technické v Praze |
| Title: | Brlek-Reutenauer Conjecture |
| Abstract: | (spoluautoři: E. Pelantová, Š. Starosta) Srečko Brlek and Christophe Reutenauer conjectured in their recent paper that any infinite word u with language closed under reversal satisfies the equality $2D(u)=\sum_{n=0}^{+\infty}T_n(u)$ in which $D(u)$ denotes the defect of $u$ and $T_n(u)$ denotes $C(n+1) - C(n) + 2 - P(n+1) - P(n)$, where $C$ and $P$ are the factor and palindromic complexity of the infinite word $u$, respectively. Brlek and Reutenauer verified their conjecture for periodic infinite words. We will prove the conjecture for uniformly recurrent words. Moreover, we will summarize some further results related to the conjecture and also some open problems related to defect. Finally, we will present a generalization of the Brlek-Reutenauer conjecture for theta-palindromes. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož