Molecular computing is viewed here as a process of writing on molecules while they are dissolved in water. When DNA molecules are employed, they are used only in double stranded form and only as data registers. All computations are initialized with the same single molecular variety. Current progress toward laboratory prototyping of computations is reported.

Let C be a finite set of n words having total length L where all words are taken over a R-element alphabet. The set C is called numerically decipherable if any two factorizations of the same word over the given alphabet into words in C have the same length. An O(nL/sup 2/) time and O((n+k)L) space algorithm is presented for computing the finest homophonic partition of C provided that this set is numerically decipherable. The latter property can be decided by another algorithm requiring O(nL) time and O((n+k)L) space. The two algorithms are based on a technique related to dominoes.

An O(n/sup 2/L) time and O((n+k)L) space algorithm is provided for deciding whether or not a finite set C consisting of n words having total length L, where all words are taken over a k-element alphabet, is a multiset decipherable code. The algorithm is based on a technique related to dominoes. At an easily stage it decides in O(nL) time and O((n+k)L) space whether or not the set C is uniquely decipherable.>