Distributional String-Rewriting

The distributional word problem for Thue systems was shown to be complete for DistNP by Wang and Belanger [WB95]. Recall that denotes the probability distribution on instances of the distributional word problem for Thue systems.

Proof.use the standard nondeterministic one-tape single-headed Turing machines as in the proof of Theorem 5.1. Let be a distributional problem in DistNP. Then there is a (nondeterministic) Turing machine that accepts in polynomial time. Without loss of generality, we assume that all the computation paths of are bounded by a polynomial of the length of inputs. By the Distributional Controlling Lemma, there is a total, one-one, p-time computable and p-time invertible function such that for all . Let .

We now construct a Turing machine with only one halting state. takes input and determines whether for some . This can be done in time polynomial in . If is not defined, then goes into an infinite loop state, otherwise, simulates on . If on reaches an accepting state, then erases all the tape symbols, moves the head to the left, and halts. If on reaches a rejecting state, then simply goes into an infinite loop.

Let . Clearly for all , on input has a halting computation if and only if accepts . Because of the time bound on , it is easy to see that if on input halts, then the number of steps it takes is bounded by a polynomial of .

Now we construct a set of productions to describe instantaneous descriptions (ID's) . Let be the halting state of , the initial state of , the blank symbol, the set of states of , and the transition function of . We use a symbol $ as an end marker to handle the blank tape detail. consists of the following ordered pairs (productions):

1. For any , , , if , then contains , and .

2. For any , , , and , if , then contains , and for , or .

We can now construct a Thue system . Let , where the are new symbols. We use these new symbols to handle nondeterminism in case the inverse of a production is applied. Let , and fix a dynamic binary coding scheme for and the finite set . We know that the length of a coded symbol is . As before, for any word on , we use to denote the coded form of .

will consist of the following (unordered) pairs:

1. (Group I) For each and each , includes .

2. (Group II) For each , includes .

3. (Group III) For each , , includes .

4. (Group IV) For each , includes .

Now consider strings and . From conditions 3 and 4 in the coding scheme, using the productions in Group I we can transform into without miscoding the already coded strings. Moreover, starting from string , the only productions that can be applied are the ones from Group I because of condition 3 in the coding scheme, and the only way to do it (which will transforms to eventually) is to start from and the leftmost symbol of . Notice that when a production in Group I is applied, it must start from a coded symbol and the leftmost symbol of the rest of the non-coded string of . Note that the productions in Group II may be applied before has been completely transformed to . Let be the number of times of applying productions in Group I to transform to .

Assume that halts on . Using productions from Group I, can be transformed into in steps. Then, using the productions from Group II that duplicate the steps of that will halt on , and using the productions from Group III as necessary, can be transformed into . After each application of a Group II production, it will be necessary to apply at most Group III productions to move the symbol as far left as possible. So transforming into will take at most steps. Finally, can be transformed into in steps by Group IV productions.

Conversely, if can be transformed into , then will halt on . It is important to note that the productions from Group II may undo a simulated step of , but since each simulated step is kept track of through the 's, it can only bring the string back to a previous simulated ID of .

So we have halts on input if and only if .

Let . Then clearly is one-one, and p-time computable. We also know that accepts if and only if halts on in time if and only if .

Now we verify that . Notice that the length of each production in is bounded by , and the number of productions in is independent of input . Notice also that , , and for some polynomial . Since , is bounded by a polynomial of . So there is a polynomial such that . Hence, . This completes the proof.

To show that the distributional common ancestor and descendant problems are complete for DistNP, we first consider a restricted version of the word problem in which is required to be an even integer as part of the instance. Clearly, the proof of Theorem 5.5 carries out easily to this restricted version as we can simply select the polynomial to be even. Hence, the restricted distributional word problem for Thue systems is complete for DistNP. The desired reduction from the restricted distributional word problem for Thue systems to the distributional common ancestor problem is defined by . Since the rewriting rules in can go both ways, it is easy to see that is a positive instance of the distributional word problem iff is a positive instance of the distributional common ancestor problem. The desired property of domination for distributions is obviously satisfied. The very same reduction applies to the distributional common descendant problem. This proves the following result [Wan95b].