Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418495 | Discrete Applied Mathematics | 2012 | 6 Pages |
Abstract
In [Š. Holub, K. Saari, On highly palindromic words, Discrete Appl. Math. 157 (2009) 953–959] the authors proposed to measure the degree of “palindromicity” of a binary word ww by ratio |rws||w|, where the word rwsrws is minimal-palindromic–that is, does not contain palindromic subwords of length greater than ⌈|w|2⌉–and the length |r|+|s||r|+|s| is as small as possible. It was asked whether the words of a given length nn which reach the maximal possible ratio |rws||w| among the words of length nn are always palindromes. It was further asked whether it can be assumed, w.l.o.g., that rr and ss are of form 0∗0∗ or 1∗1∗, or at least 0∗1∗0∗1∗ or 1∗0∗1∗0∗. We negatively answer these questions, and also one further question of a similar kind.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bojan Bašić,