Closures versus Freeness


In the literature one finds two views on rewriting:

  1. as relations (Dershowitz & Jouannaud, Klop, Baader & Nipkow, Ohlebusch,...), and
  2. as systems (Newman,Hindley, Melliès,Khasidashvili,...).

We argue that it is interesting to systematically connect both views, supported by various simple examples. For instance, reducibility (the reflexive--transitive closure) in view 1 is connected to reduction (a certain free construction) in view 2. After discussing several such basic examples, we present the general pattern, with as basic intuition that view 1 corresponds to closure properties (to adjectives: reducibility, convertibility,...), and view 2 to free constructs (to nouns: reduction, conversion, ...), and conclude with discussing how this connexion is helpful, leads to new results and rewrite theory.