2
$\begingroup$

I've been reading Don Gusfield's "Algorithms on Strings, Trees, and Sequences", and quite a some chunk of the textbook concentrates on palindromic-related ideas.

I'm unsure as to whether this is because the question is purely theoretically interesting (in terms of finding good lower bounds), or there are practical use cases for this (in terms of genetics, or even other use cases I don't know of).

So, what do studying palindromes offer us? Do they offer theoretical insight into other string problems --- the way matrix multiplication and matrix inversion offer insights into each other? Are they practically useful? Or is it "just fun"?

$\endgroup$
2
$\begingroup$

I had a use for palindromes as follows:

A string of length $n$ and its reversal have the same complexity. Thus, when studying complexity of strings you can identify a string with its reversal.

Now after identifying you may ask how many equivalence classes have certain properties. And then the number of equivalence classes is directly related to the number of palindromes. If there are $p_n$ palindromes then there are $$p_n+(2^n-p_n)/2$$ equivalence classes of binary strings.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.