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$

closed as too broad by D.W., David Richerby, Juho, Rick Decker, Luke Mathieson Dec 1 '14 at 1:53

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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