Although the set of reachable states of a lossy channel system (LCS)
is regular, it is well-known that this set cannot be constructed
effectively. In [ABB01], one characterizes significant classes of
LCS for which the set of reachable states can be computed.
Furthermore, it is shown that, for slight generalizations of these
classes, computability can no longer be achieved. To carry out this
study, one defines rewriting systems which capture the behavior
of LCS, in the sense that (i) they have a FIFO-like semantics and (ii)
their languages are downward closed with respect to the substring
relation. The main result of the paper shows that, for context-free
rewriting systems, the corresponding language can be computed. An
interesting consequence of this result is that it yields a
characterization of classes of meta-transitions whose post-images can
be effectively constructed. These meta-transitions consist of sets of
nested loops in the control graph of the system, in contrast to
previous works on meta-transitions in which only single loops are
considered. Essentially the same proof technique we use to show the
result mentioned above allows also to establish a result in the theory
of 
-systems, i.e., context-free parallel rewriting systems. It is
proven that the downward closure of the language generated by any
-system is effectively regular.