Reducing a set of non-unique elements via transformations

Question

I have:

1) a "starting set", a multiset, e.x. { x, y, z, z },

2) a set of transformations, e.x. {x,z} => {y}, {z,z} => {z}, {x} => {z}, {y} => {x}, and

3) a "target set" that I am trying to get by applying transformations to the starting set, e.x. { z }.

I'd like to find an algorithm to generate the (possibly infinite) possible applications of the transformations to the starting set that result in the target set. For example:

{ x, y, z, z }, y => x
{ x, x, z, z }, x => z
{ z, x, z, z }, x => z
{ z, z, z, z }, {z, z} => z
{ z, z, z }, {z, z} => z
{ z, z }, {z, z} => z
{ z }

The order of the elements is irrelevant everywhere.

This sounds like something that's probably an existing (named) problem, but I don't recognize it. Can anyone help me track it down, or suggest further reading on something similar?

Answer 1

You are describing a very broad problem. It can be solved in the general sense by doing a breadth first search (depth first won't work if the transformations are non-terminating), just apply all rules you can in a breadth first order until you hit the target set.

Performance will probably be poor, more can ofcourse be gained by thinking more of the semantics of the transformations. Reducing the current state to its smallest but equivalent form after each rewrite and defining a search strategy and using A* can help you.

Answer 2

This seem to be a very hard problem! I believe that even the decision problem to determine if a sequence of transforms exists (to convert source to target) is an Undecidable Problem. Look at the Tag System page on the page of List of Undecidable Problems.

In fact, it looks like the decision verion of your problem is at least as hard as the Collatz Conjecture, which states that the sequence

n -> n/2 if n is even
n -> 3n+1 if n is odd

always ends in 1.

This conjecture can be stated as:

given the set of transforms

a -> bc
b -> a
c -> aaa

Can the word

aaa...aaa (a repeated n times)

eventually be transformed to the word

a

(The single letter a).

Since the transformations only take one character at a time, the order does not matter: a word can be viewed as a multiset and is applicable to your problem.

This set of transforms for the Collatz Conjecture was gotten from here: http://logica.ugent.be/liesbeth/TagColOK.pdf (see page 7).

Basically we cannot even be sure if any algorithm for this particular problem will ever terminate on all inputs.

I guess you just need to explore all paths (using BFS/A* whatever) and hope you get lucky.

Of course, if your rules of transformation always reduced the number of symbols, then an exhaustive search (even DFS) would surely halt.

So, as you said, do a BFS/heuristic. But, now after this information, I guess you can do it confidently. :-)