Reversals
Problem: Let S be a string of length n over alphabet set {1,...,k}. The operation one is allowed to do is to replace any X X^R by X, where X^R is the reverse of X. Determine the smallest resulting string by applying this operation any number of times.
Commentary: If k=2, this can be solved. Also, if the operation is to delete the entire X X^R, then the problem is solvable. The problem may belong to some general algebraic theory?
Commentary: If k=2, this can be solved. Also, if the operation is to delete the entire X X^R, then the problem is solvable. The problem may belong to some general algebraic theory?
posted by metoo at 7:40 AM
3 Comments:
What is it about k=2 that makes the problem easier than when k=3? Usually the choice of Turing Machine alphabet just changes the difficulty of a problem by a constant factor.
Hi Muthu,
For some reason, this problem reminds me of a cute little number theory conjecture that people have mulled about (and to the best of my knowledge haven't gotten very far)... the problem is to take a number and add this to the reverse of it's digits. Do the same to the resulting number and so forth. The conjecture is that in some finite number of steps, the resulting number will be a palindrome.
this sounds like something from the realm of free groups ?
Post a Comment
<< Home