We first consider the word problem for Thue systems. This
problem was first studied
in modern algebra by Thue [Thu14].
Wang and Belanger [WB95] studied
its bounded version with uniform distributions
on instances.
Let 
be a non-empty finite alphabet. An ordered pair
of strings on alphabet
is called a
production (rule, or rewriting rule).
It is customary to write the production in the form
. Let 
and 
be two strings.
Let be a production. Write
(omitting when there is no ambiguity)
if 
and 
for (possible null) strings 
and 
.
Let 
be a set of productions. Then write 
if 
for some 
. Write 
if there is a finite sequence: 
for 
.
The inverse of the production is the production
. A Thue system is a non-empty set of productions
such that
for each 
, the inverse of 
is also in . Write
to denote both the production and
its inverse.
Let be a Thue system. Let and be two strings. Then
iff 
. So we write 
if . We write 
if there is a finite sequence: 
for . We write 
if there exists an 
such that
.
This is an equivalence relation, and set of equivalence classes form a
monoid under the operation of concatenation.
Let 
be a finite set of strings. We use
to denote 
and
to denote 
.
DISTRIBUTIONAL WORD PROBLEM FOR THUE SYSTEMS
Instance. Thue system 
of 
productions, two
binary strings , , and a positive integer ,
where 
's and 
's are binary strings.
The size of the instance is 
.
Question. Is ?
Distribution. Randomly and independently choose positive integers
, , and binary strings , . Then randomly an
d independently
choose binary strings 
. The
random choices are made with respect to the default uniform
probability distributions on positive integers and binary strings.
Hence, the probability distribution 
is proportional to
The distributional word problem for Thue systems was shown to be average-case NP-complete by Wang and Belanger [WB95].
Next, we consider other string rewriting problems.
A set of productions is also called a string-rewriting
system, in which the inverse of a production
does not need to be in the system. We can similarly define
the distributional word problem for semi-Thue systems on
string-rewriting systems, which is average-case NP-complete [WB95].
The reader is referred to
[BO93] for a comprehensive introduction to
string-rewriting systems.
DISTRIBUTIONAL COMMON ANCESTOR PROBLEM
Instance. A string-rewriting system 
of rewriting rules,
two binary strings
and 
, and a positive integer .
The size of the instance is 
.
Question. Is there a binary string 
such that 
and 
?
Distribution. The same as 
.
DISTRIBUTIONAL COMMON DESCENDANT PROBLEM
Instance. A string-rewriting system , two binary strings
and , and a positive integer .
The size of the instance is .
Question. Is there a binary string such that 
and 
?
Distribution. The same as .
These two string-rewriting
problems were shown to be average-case NP-complete by
Wang [Wan95b].
