G. Caltais, E.-I. Goriac, D. Lucanu, G. Grigoras

ROC! is a deterministic rewrite strategy language which includes the rewriterules as basic operators, and the deterministic choice and the repetitionas high-level strategy operators. In this paper we present a method which,for a given term rewriting system (TRS) R, constructs a new TRS R’ such thatR’-rewriting is equivalent (sound and complete) with R-rewriting constrained byROC!. Since R’ uses a stack, it is called a rewrite stack machine.

Full Document (PDF)


author = "G. Caltais and E.-I. Goriac and D. Lucanu and G. Grigora{c s}",
title = "{A} {R}ewrite {S}tack {M}achine for {R}{O}{C}!",
institution = "``Al.I.Cuza'' University of Ia{c s}i,     Faculty of Computer Science",
year = "2008",
number = "TR 08-02",
note = "URL:http://www.infoiasi.ro/~tr/tr.pl.cgi"}