5
$\begingroup$

I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references.

Let $A$ be a finite set of symbols, are there efficient algorithms that take as input a word $w$ over $A$ and return as output a representation of $w$ in terms of product of powers? If so, what are their computational complexities?

Of course, this representation is not unique, for example for $A = \{0,1\}$ we have $$0101010010010 = (01)^3 (001)^2 0 = (01)^2 (010)^3 ,$$ so they might be algorithms that impose further restrictions on the exponents or on the lengths of the bases of the powers.

Also, to avoid trivialities, if $w$ can be written as a product of powers of words with at least a power with exponent $>1$, then such algorithms should be able to find one of such representations (otherwise, obviously, we always have $w = w^1$).

Thanks for help.

$\endgroup$

1 Answer 1

3
$\begingroup$

Unfortunately, I couldn't easily find a paper that solves exactly this problem.

But I believe the algorithm from Factorizing Strings into Repetitions can be adapted to solve the problem. They find a factorization into repetitions, meaning that $s = s_1 s_2 \dots s_k$, where each factor $s_i$ can be represented as $s_i = x^k x'$ for some string $x$, where $k \geq 2$ and $x'$ is a prefix of $x$.

Their algorithm consists of an efficient dynamic programming simulation and it likely can be modified to get rid of $x'$ and $k \geq 2$ constraint, while asking for the minimum number of factors.

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