Conventional and Uniqueness Typing in Graph Rewrite Systems Erik Barendsen & Sjaak Smetsers University of Nijmegen Computing Science Institute Toernooiveld 1 6525 ED Nijmegen The Netherlands e-mail erikb@cs.kun.nl, sjakie@cs.kun.nl fax +31.80.652525 ABSTRACT In this paper we describe a Curry-like type system for graphs and extend it with uniqueness information to indicate that certain objects are only `locally accessible'. The correctness of type assignment guarantees that no external access on such an object will take place in the future. We prove that types are preserved under reduction (for both type systems) for a large class of rewrite systems. Adding uniqueness information provides a solution to two problems in implementations of functional languages: efficient space management and interfacing with non-functional operations. AMS Classification (1991): 68Q42 (68Q05). CR Classification (1991): F.4.2, D.3.3 (D.3.1, D.1.1, F.4.1). Keywords and phrases: graph rewrite systems, functional programming languages, typing, higher order functions, uniqueness typing, algebraic types, linear typing, destructive updates.