Find minimum number of transformations to transform from input to target string

Question

Given that I have an input string, for example: aab
And I am given a target string, for example: bababa
And then I am given a set of transformation rules. For example:

ab -> bba
b -> ba

There can be N rules.
The characters for the input and output string don't have to be just a and b, they can be any characters.

How could I do an algorithm that would find the minimum number of transformations that would need to be applied in the input string to get the target string.

In this example, for example, the number would be 3. Because we would do:

1 - Apply rule 1 (abba)
2 - Apply rule 1 again (bbaba)
3 - Apply rule 2 (bababa)

It could happen that given an input and a target, there is no solution and that should be noticed too.

Also, it can be that the target string is shorter than the input string.

I am pretty much lost in strategies on doing this. It comes to my mind creating an automata but I am not sure how would I apply in this situation. I think is an interesting problem and I have been researching online, but all I can find is transformations given rules, but not how to ensure it's a minimum.

Thanks

Answer 1

EDIT

As noted by usul, my previous answer is too broad, so these are some additional notes with personal ideas (so it is now more like an extended comment, than an answer):

If the given grammar is context sensitive, the alphabet has size >= 2 and there are no limits in the number of transformations, then even the problem of deciding if the grammar generates the target string is undecidable. You can easily find a grammar that simulates a NTM; as pointed out by Jeffe Markov algorithms are Turing complete, so given a TM and a string w you can build a grammar and a source string that generate a target string iff TM halts on w. So finding the minimum is undecidable, too.

If you put a limit in the number of transformations (polynomial), then the problem of deciding if the grammar generates the target string is PSPACE complete, and the problem of finding the minimum number of transformations is surely harder.

If the number of transformations is fixed, I think that the the problem is NP complete (I've a fuzzy idea of a quick reduction from monotone NAE-3SAT)

I leave the previous answer below.

The problem of finding the smallest CFG grammar that generates a given string (also known as Minimum Grammar Compression or MGC) is NP-complete (J. Storer, "NP-completeness results concerning data compression", 1977).

I think that the complexity of the problem when the alphabet is restricted to $\{0,1\}$ (2-MGC) is still unknown.

If you switch to context sensitive grammars (LBAs) then you can look at resource-bounded Kolmogorov complexity. Unlike the unbouded Kolmogorov complexity, finding the smallest program that computes a given string is decidable, but we are obviously nearby intractability. There is a lot of reasearch on the subject (and many open problems); for example consider a binary string of length $2^n$ that represents the truth table of a boolean function $f$ and an integer $s$; the complexity of deciding if there is a boolen circuit of size at most $s$ that computes $f$ is unknown (probably not in $P$ but also unlikely to be NP-complete). Here it is a simple introduction and a very nice paper on the power of random strings.

Answer 2

I think the question is not yet quite precise, but let me give a couple ways it could be made precise and an answer for each.

---

1) We are given an "input string" $s$, an "output string" $t$, a set of pairs $F = \{(a,b) : \text{$a$ and $b$ are strings}\}$, and an integer $k$. The question is if there exists a sequence of pairs $(a_1,b_1),\dots,(a_n,b_n)$ such that: (1) each $(a_i,b_i) \in F$; (2) $a_1 = s$; (3) $b_n = t$; (4) for each $2 \leq i \leq n$, $a_i = b_{i-1}$; (5) $1 \leq n \leq k$.

In English, the $(a_i,b_i) \in F$ are "transformations" taking an input string to an output string, and we want to know if there is a length-$k$ or shorter sequence of transformations turning the input into the output.

This can be solved in polynomial time by Dijkstra's algorithm for shortest paths. Make $s, t$, each $a_i$, and each $b_i$ nodes in a graph, drawing a directed edge of length $1$ between $a_i$ and $b_i$ for each $(a_i,b_i) \in F$. There is a length-$k$ transformation of $s$ to $t$ if and only if there is a path of length $k$ between them in the graph.

---

2) We are given an input string, output string, and context-free grammar, and asked if the grammar generates the output string from the input string in a parse tree of $k$ or fewer nodes. In this case, the decision problem of whether any derivation exists can be solved in polynomial time but I am not sure about the problem of smallest derivation.

---

3) Same question but for a context-sensitive grammar. In this case, the decision problem of whether there exists a derivation at all is PSPACE-complete. I am not sure about complexity of finding a shortest derivation.

---

4) Same question but for an unrestricted grammar. In this case, even the question of whether there exists a derivation is undecidable.