From Linear Term Rewriting to Graph Rewriting with Preservation of Termination

Roy Overbeek, Jörg Endrullis

Encodings of term rewriting systems (TRSs) into graph rewriting systems usually lose global termination, meaning the encodings do not terminate on all graphs. A typical encoding of…