
Event structures are a widely accepted model of concurrency. In a seminal
paper by Nielsen, Plotkin and Winskel, they are used to establish a bridge
between the theory of domains and the approach to concurrency proposed by
Petri. A basic role is played by an unfolding construction that maps (safe)
Petri nets into a subclass of event structures where each event has a uniquely
determined set of causes, called prime event structures, which in turn can be
identified with their domain of configurations. At a categorical level, this is
nicely formalised by Winskel as a chain of coreflections. Contrary to prime
event structures, general event structures allow for the presence of
disjunctive causes, i.e., events can be enabled by distinct minimal sets of
events. In this paper, we extend the connection between Petri nets and event
structures in order to include disjunctive causes. In particular, we show that,
at the level of nets, disjunctive causes are well accounted for by persistent
places. These are places where tokens, once generated, can be used several
times without being consumed and where multiple tokens are interpreted
collectively, i.e., their histories are inessential. Generalising the work on
ordinary nets, Petri nets with persistence are related to a new class of event
structures, called locally connected, by means of a chain of coreflection
relying on an unfolding construction.

Stable event structures, and their duality with prime algebraic domains
(arising as partial orders of configurations), are a landmark of concurrency
theory, providing a clear characterisation of causality in computations. They
have been used for defining a concurrent semantics of several formalisms, from
Petri nets to linear graph rewriting systems, which in turn lay at the basis of
many visual frameworks. Stability however is restrictive for dealing with
formalisms where a computational step can merge parts of the state, like graph
rewriting systems with nonlinear rules, which are needed to cover some
relevant applications (such as the graphical encoding of calculi with name
passing). We characterise, as a natural generalisation of prime algebraic
domains, a class of domains that is wellsuited to model the semantics of
formalisms with fusions. We then identify a corresponding class of event
structures, that we call connected event structures, via a duality result
formalised as an equivalence of categories. Connected event structures are
exactly the class of event structures the arise as the semantics of nonlinear
graph rewriting systems. Interestingly, the category of general unstable event
structures coreflects into our category of domains, so that our result provides
a characterisation of the partial orders of configurations of such event
structures.

We investigate three formalisms to specify graph languages, i.e. sets of
graphs, based on type graphs. First, we are interested in (pure) type graphs,
where the corresponding language consists of all graphs that can be mapped
homomorphically to a given type graph. In this context, we also study languages
specified by restriction graphs and their relation to type graphs. Second, we
extend this basic approach to a type graph logic and, third, to type graphs
with annotations. We present decidability results and closure properties for
each of the formalisms.

This volume contains the proceedings of TERMGRAPH 2016, the Ninth
International Workshop on Computing with Terms and Graphs which was held on
April 8, 2016 in Eindhoven, The Netherlands, as a satellite event of the
European Joint Conferences on Theory and Practice of Software (ETAPS 2016).

The relationship between Term Graph Rewriting and Term Rewriting is well
understood: a single term graph reduction may correspond to several term
reductions, due to sharing. It is also known that if term graphs are allowed to
contain cycles, then one term graph reduction may correspond to infinitely many
term reductions. We stress that this fact can be interpreted in two ways.
According to the "sequential interpretation", a term graph reduction
corresponds to an infinite sequence of term reductions, as formalized by
Kennaway et.al. using strongly converging derivations over the complete metric
space of infinite terms. Instead according to the "parallel interpretation" a
term graph reduction corresponds to the parallel reduction of an infinite set
of redexes in a rational term. We formalize the latter notion by exploiting the
complete partial order of infinite and possibly partial terms, and we stress
that this interpretation allows to explain the result of reducing circular
redexes in several approaches to term graph rewriting.

We propose a framework for the specification of behaviourpreserving
reconfigurations of systems modelled as Petri nets. The framework is based on
open nets, a mild generalisation of ordinary Place/Transition nets suited to
model open systems which might interact with the surrounding environment and
endowed with a colimitbased composition operation. We show that natural
notions of bisimilarity over open nets are congruences with respect to the
composition operation. The considered behavioural equivalences differ for the
choice of the observations, which can be single firings or parallel steps.
Additionally, we consider weak forms of such equivalences, arising in the
presence of unobservable actions. We also provide an upto technique for
facilitating bisimilarity proofs. The theory is used to identify suitable
classes of reconfiguration rules (in the doublepushout approach to rewriting)
whose application preserves the observational semantics of the net.