4
$\begingroup$

I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known.

To be more precise, let $\Sigma$ be a finite alphabet. I am looking for problems, where the input (or an important part of the input) is a set (or an ordered list) of strings $w_1,\dots ,w_m\in\Sigma^*$ (gladly $m=1$) and there are known algorithms to solve the problem in polynomial time in the length of the input strings (+ possible other input variables). It would be great to get references to the algorithms, too.

An example:
Given a nondeterministic finite automaton $M$ with $s$ states, which accepts the regular language $T(M)$ and a string $w\in\Sigma^n$. Is $w\in T (M)$? Obviously, this is possible in polynomial time in $n $ (and $s $).

Why do I want to know such problems?
I want to analyse, whether the polynomial time holds for some (possibly exponential) compressed representations of the strings in the length of the compact form or not.

I am interested in problems of all possible areas. It is also okay to post just one problem. I hope to get a bunch of interesting problems in addition.

Thanks a lot!

$\endgroup$
  • $\begingroup$ Instead of trying to get citations of known polynomial-time algorithms for problems on strings, why not consider a P-Complete problem so you can get a sense of an algorithm that anything in P can be reduced to? For strings consider the LZW compression algorithm, and when given a context free grammar and a string determining whether that grammar can generate that string. $\endgroup$ – Francesco Gramano Nov 28 '14 at 0:20
  • $\begingroup$ @FrancescoGramano I'm sorry, but I don't think that it is as simple as you think. If I find a P-complete problem in the length of an input string for which the polynomial time holds also for the compressed length, i can't follow that the same holds for all P problems. $\endgroup$ – Danny Nov 28 '14 at 10:38