On the Specification of Visual Languages: Multisets as First-Class Citizens

We propose a new paradigm for the specification of the syntax and semantics of visual languages, where multisets, contrary to so far existing works, are integrated as first-class citizens, in the sense that they can be manipulated without any limitation. We show that the resulting systems, called multiset rewriting systems, are extremely expressive for reasoning about multidimensional objects. Moreover, we provide a thorough analysis of their properties, like confluence and termination, and of their possible extensions.