This paper introduces a general notion of static-port graph grammar (PGG) that encompasses existing formalisms that have been independently proposed, such as linear graph grammars, interaction nets and partial sharing graphs. These formalisms provide a computational framework for asynchronous computation that respects a very rigorous notion of local interaction, and have proven a suitable basis for the internal representation of program and data in the compilation of high-level programming languages for distributed execution. The general class of PGGs introduced in this paper provides a more expressive computational framework, still possessing asynchronous concurrency but which has a reduction mechanism that is complex and non-local. The increased expressiveness of this calculus is shown by means of a motivating example of concurrent pattern matching. However, the nonlocality of the calculus renders it unsuitable for direct implementation. The paper introduces a class of simple PGGs, a local rewriting calculus suitable for distributed implementation. The central result of the paper is to show how the general class of PGGs may be reduced to the simple PGGs, in a manner that fully preserves all the potential for concurrent rewriting present in the original. # 2002 Elsevier Science (USA) * Alan Bawden proposed a framework in 1986, initially by the name 'Connection graphs,' as a programming language for distributed computation based on his experience with the massively parallel Connection Machine at MIT [Baw86, Hil85]. His Ph.D. thesis develops the idea further (now calling * *