I know that the word problem is undecidable in general, but I would like to know about a related but similar problem which is: given a free monoid with a set of rewriting rules, and a string from that monoid, determine the number of elements in that string's equivalence class. This seems less powerful to know than whether 2 strings are in the same equivalence class, so I have hope that it is tractable.
I would like to know:
- Is it decidable?
- If it is decidable, how can it be done?
- Can it be done for this specific free monoid: (Alphabet of {p, q, 0}, rewriting rules: pq=0p, qp=0q), and if so, how?
I really only care about the solution for the free monoid in point 3, but a general solution could be applied to it so it would also be useful.
What I have found so far - All equivalence classes have a normal form, consisting of some number of p's or q's followed by a p, a q, or a 0. For example: ppqqp is in normal form, as is pqpq0, but p0qpq is not. All words can be generated from the normal forms by exclusively increasing the number of 0s in the string, that is never applying the given rewriting rules in reverse.