(Cyclic) Term Graph Rewriting is adequate for Rational Parallel Term Rewriting
"Acyclic" Term Graphs are able to represent terms with sharing,
and the relationship between Term Graph Rewriting (TGR)
and Term Rewrtiting (TR) is
now well understood. During the last years, some
researchers considered the extension of TGR to possibly "cyclic"
term graphs, which can
represent possibly infinite, rational terms. In [Kennaway et.al.,1994]
the authors formalize the classical relationship between TGR and TR as an
"adequate mapping" between rewriting systems, and extend it by
proving that unraveling is an adequate mapping from cyclic TGR to
rational, infinitary term rewriting: In fact, a single graph
reduction may correspond to an infinite sequence of term reductions.
Using the same notions, we propose a different adequacy result,
showing that unraveling is an adequate mapping from cyclic TGR to
"rational parallel term rewriting", where at each
reduction infinitely many rules can be applied in parallel.
We also argue that our adequacy result is more
natural than that proposed in [Kennaway et.al.,1994], because
the length of the
reduction sequences is preserved by unraveling, and collapsing rules
are treated in a completely uniform way.