Specifying Visual Languages with Conditional Set Rewrite Systems

We propose Conditional Set Rewriting as a general mechanism for describing the syntax of multidimensional languages. We compare the approach with other existing methods, and give a number of examples that illustrate its strengths. 1 Introduction This paper introduces the notion of a Conditional Set Rewrite System (CSRS). Conditional Set Rewrite Systems are a generalization of Conditional Term Rewrite Systems [10]. Conditional Term Rewrite Systems deal with rewriting a single term, whereas Conditional Set Rewrite systems deal with rewriting a set of terms. Each conditional set rewrite rule specifies how to replace a subset of the set of terms by another set. We suggest two uses for CSRS: they can be used to describe the set of all legal phrases (pictures) of a multidimensional (visual) language, and they can be used to translate a phrase from one language (e.g. a visual one) into another language (e.g. a textual one). The ability of CSRS to translate visual programs into textual ones ..