MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Building optimal rewriting rules.

I have two alphabets A and B. A have a dictionary which contains words in A together with their translation in B (ie. the dictionary is a map from symbols [a1, a2, ..., an] to [b1, b2, ..., bm]). I need an algorithm that will construct an optimal rewriting system which will rewrite a-symbols into b-symbols. The rewriting system is optimal if it preservers maximal number of pairs. (Of course there must be limit to the number of rewriting rules).

The motivations is in speech processing. I have a set of rules and a large directory for text-to-phoneme transformation and I want to build rules fro phoneme-to-text transformation.

-
Somehow I suspect that StackOverflow maybe a better place to post this question. Unless you are looking for a provably optimal system... – Willie Wong Jul 4 2010 at 19:39
Could you clarify what you mean by optimal? And precisely what your rewrite system should do? Undecidability abounds with rewrite systems, such as the Post systems and others. – Joel David Hamkins Jul 4 2010 at 19:45
@Joel David Hamkins: My rewrite system should be a set of rewrite rules that applied recursively on an a-word replace all a-symbols with b-symbols. Optimality: my dictionary has, say 10000 word pairs (a_i,b_i). The system S1 is better than S2 if S1 creates more matches (ie. S1(a_i) = b_i) than S2 on the particular dictionary. – danatel Jul 4 2010 at 20:22
But I could design a rewrite system that consults the dictionary and does it perfectly, right? So it seems that you are likely asking actually about the best possible system with respect to some resource limitation? And does the system have to recognize the domain language? That is, your criterion doesn't seem to punish it for providing translations of words not in the first language. And must it be determinisitic (that is, always give the same translation for a given word)? – Joel David Hamkins Jul 4 2010 at 21:24
it sounds like the OP's question can be reformulated this way: given a limit K on the number of rules, maximize the number of pairs a_i, b_i mapped correctly by the rule system, where the rules can apply recursive, so if 11 <-> aa and 1123 <-> aabc, then the rule S(11)=aa captures the first map and the first part of the second map. Obviously K < min(n,m). – Suresh Venkat Jul 5 2010 at 8:06