Modelling, specifying and reasoning about complex systems requires to process in an integrated fashion declarative and procedural aspects of the target domain. The paper reports on an experiment conducted with a propositional version of Logic Programming Petri Nets (LPPNs), a notation extending Petri Nets with logic programming constructs. Two semantics are presented: a denotational semantics that fully maps the notation to ASP via Event Calculus; and a hybrid operational semantics that process separately the causal mechanisms via Petri nets, and the constraints associated to objects and to events via Answer Set Programming (ASP). These two alternative speci cations enable an empirical evaluation in terms of computational e ciency. Experimental results show that the hybrid semantics is more e cient w.r.t. sequences, whereas the two semantics follows the same behaviour w.r.t. branchings (although the denotational one performs better in absolute terms).
A proper treatment of cases or scenarios is based on two requirements: on the one hand, to capture and adequately process the symbolic entities used to represent the target system: instances, classes, interrelationships forming a local ontology relevant to the domain in focus; on the other hand, to reproduce|by means of elements modelling causal mechanisms, processes, courses of actions, etc.|the same dynamics exhibited by the target system.
Consider for example this case: \While John was walking his dog, the dog ate Paul's owers." This event description is not su cient for entailing that John is responsible to pay Paul for what happened, as typically this is concluded on the basis of norms as \The owner of an animal has to pay for the damages it produces.' '. However, even this addition lacks crucial connections between the *Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). conceptual domain of the case and the one of the norm, like \dogs are animals ", \eating an object destroys the object ", \destruction is damage", etc.
These various elements exhibit two perspectives on knowledge: a declarative
perceptive, concerning objects (physical, mental, institutional) and their logical
relationships|both rei ed as symbols|; and a procedural perceptive,
concerning patterns of events/actions, mechanisms, or processes (involving objects) (cf.
reactive/declarative dichotomy in [
Rather than trying to project one dimension on the other, an alternative
tradition in AI and logic proposes to consider causality as a primitive notion. This
approach is for instance behind the idea of all Action languages [
The motivation behind this work stems from the hypothesis that leaving process analysis to procedural descriptions should be in principle a better choice: procedural components can directly map to native computational mechanisms, that can be used not only to re-present, but also re-create the process object, transforming the question from what the referent should be (characteristic of logic), to what it is (characteristic of simulation and more in general of modelexecution).
The paper reports therefore on a simple benchmark experiment with an
hybrid notation (that is, including procedural and declarative knowledge
components), called Logic Programming Petri Nets (LPPNs).1 Section x 2 will introduce
the motivation and an informal semantics of LPPNs. Section x 3 will present a
formalisation of a propositional version of LPPN. Section x 4 will present an
hybrid operational semantics and a denotational semantics based on ASP
programs with Event Calculus. Section x 5 will present the results of a rst empirical
experiment. Discussion and a note on further developments end the paper.
1 A prototype of a LPPN interpreter is available on http://github.com/s1l3n0/
pypneu, together with the code run for conducting the experiment.
(a) not enabled transition, (b) enabled transition and (c) the transition has red
before ring ring
Logic Programming Petri Nets (LPPNs) are a visual notation rst introduced in
[
Despite their widespread use in computer science, electronics, business
process modelling and biology, Petri nets are generally considered not to be enough
expressive for reasoning purposes: in their simplest form, tokens are indistinct,
2 For an overview on the general properties of Petri nets see e.g. [
AND
(a) p7
E
t2
p9
p8
(b)
t3
E
t4
p10
p11
and do not transport any data. Nevertheless, it is a common practice for
modellers to introduce labels to set up a correspondence between the modelling
entities and the modelled entities. This practice enables them to read the results of
a model execution in reference to the modelled system. In other words, an
adequate labelling is still functional to the use of a Petri net for modelling purposes,
although it is not a requirement for the execution in itself. Further interaction
is possible if these labels are processed according to an additional formalism, as
for instance it occurs with Coloured Petri Nets (CPNs) [
Whereas Petri nets essentially specify procedural mechanisms, Logic Programming Petri Nets (LPPNs) extend those (a) with literals as labels, attached on places and transitions; (b) with nodes specifying (logic-programming based) declarative bindings on places and on transitions. For simplicity, this paper will focus only on propositional labelling. Under this constraint, the execution of the LPPN procedural component is the same as Condition/Event nets, Petri nets whose places do not contain more than one token (Fig. 1). Logic operator nodes might apply on places (lp-nodes) or on transitions (lt-nodes). An example of a sub-net with lp-nodes (small black squares) is given in Fig. 2a; these are used to create logic compositions of places (via operators as NEG, AND, OR, etc). or to specify logic inter-dependencies (via the logic conditional IMPLIES). Similarly, transitions may be connected declaratively via lt-nodes (black circles), as in Fig. 2b; these connections may be interpreted as channels enabling instantaneous propagation of ring. In this case, it is not relevant to introduce operators as AND, for the interleaving semantics, only one source transition may re per step. Operationally, the declarative components are treated integrating the stable
model semantics used in answer set programming (ASP) [
This section presents a simpli ed version of the LPPN notation considering only
a propositional labeling. We start from the de nition of propositional literals
derived from ASP [
De nition 3 (Propositional Logic Programming Petri Net). A propositional Logic Programming Petri Net LPPN prop is a Petri Net whose places and transitions are labeled with literals, enriched with declarative nets of places and of transitions. It is de ned by the following components: { hP; T; PE i is a procedural net; PE stands for procedural edges; { CP : P ! L and CT : T ! L are labeling functions, associating literals respectively to places and to transitions; { OP = f:; ; ^; _; !; $; : : :g is a set of logic operators. { LP and LT are sets of logic operator nodes respectively for places ( lp-nodes) and for transitions ( lt-nodes). { CLP : LP ! OP maps each lp-node to a logic operator; similarly, CLT :
LT ! OP does the same for lt-nodes. { DE LP = DE L+P [ DE LP is the set of arcs connecting lp-nodes to places; similarly, DE LT = DE L+T [ DE LT for lt-nodes and transitions.6 { M : P ! f0; 1g returns the marking of a place, i.e. whether the place contains (1) or does not contain (0) a token.
Note that if LP [ LT = ?, we have a strictly procedural LPPN prop, i.e. a standard binary Petri net. If T = ?, we have a strictly declarative LPPN prop, that can be directly mapped to an ASP program. For simplicity, we overlook in this document the syntaxic constraints on the network topology which are inherited from ASP. 4
This section will present two semantics for LPPNs: a hybrid operational semantics and a denotational semantics, based on ASP and event calculus. 5 Default negation is used to reify a situation in which something cannot be retrieved/inferred (e.g. `It is unknown whether it rains or not'). 6 Note that DE LT (T [ P ) LT , i.e. these edges go from transitions and places (modeling contextual conditions) to lt-nodes.
The execution cycle of a LPPN consists of four steps: 1. given a \source" marking M , the bindings of the declarative net of places entail a \ground" marking M ; 2. an enabled transition is selected to pre- re, determining a \source" transitionevent e; 3. the bindings of the declarative net of transitions entail all propagations of this event, obtaining a set of transition-events, also denoted as the \ground" event-marking E ; 4. all transition-events are red, producing and consuming the relative tokens. The steps (1) and (3) are processed in distinct moments and programs by an ASP solver: the declarative nets of places (1) or of transitions (3) are translated as rules, tokens (1) or source transition-events (3) are rei ed as facts. The ASP solver takes as input the resulting program and, if satis able, it provides as output respectively one or more ground marking (1) or one or more sets of transition-events to be red (3). The steps (2) and (4) make clear the distinction the external rings (the \source" transition-event selected at execution level) from the internal ring, immediately propagated (the \ground" transition-events triggered by the declarative net of transitions). The following de nitions provides a formalisation of these concepts.
De nition 4 (Enabled transition). A transition t is enabled in a ground marking M if a token is available for each input places:
Enabled (t)
8pi 2 t; M (p) = 1 Similarly to what marking is for places, we consider an event-marking for transitions E : T ! f0; 1g. E(t) = 1 if the transition t produces a transition-event e. Each step s has a \source" event-marking E.
De nition 5 (Pre- ring). An enabled transition t pre- res (implicitly, at a step s) if it is selected to produce a transition-event: 8t 2 Enabled (T ) : t pre- res
E(t) = 1 Applying an interleaving semantics for the pre- ring, the interpreter selects only one transition to pre- re per step; for any other t0, E(t0) = 0.
De nition 6 (Firing). An enabled transition t res (implicitly, at a step s) by propagation consuming a token from each input place, and producing a token in each output place:
8t 2 Enabled (T ) : t res
E (t) = 1 $ 8pi 2 t : M 0(pi) = 0 ^ 8po 2 t : M 0(po) = 1 4.2
One of the possibilities to validate a formal language is to map it into another formal language, i.e. to provide a denotational semantics. The declarative component of a LPPN, by design, can be directly rewritten as ASP code. As we are already halfway down the path, we can translate the remaining procedural component into ASP.
Event Calculus axioms A well-known solution to treat change in logic
programming is event calculus (EC) [
In ASP code: {prefiresAt(T, N)} :
enabled(T, N), transition(T), time(N). firesAt(T, N) :- prefiresAt(T, N). someTransitionPrefiresAt(N) :- % (iii) prefiresAt(T, N), transition(T), time(N). :- not someTransitionPrefiresAt(N), enabled(T, N), transition(T), time(N). :- prefiresAt(T1, N), prefiresAt(T2, N), T1 != T2, transition(T1), transition(T2), time(N). % (i) % (ii) % (iv) Transformation of a LPPN to an ASP program The mapping of a given LPPN to an equivalent ASP program includes the previous axioms and the output of the following steps: i. for each place p, with label CP (p) (a) type it as place, (b) specify its initial state, (c) for each place with more than one output, write down that you cannot consume more than the only available token. ii. for each transition t, with label CT (t) (a) type it as transition, (b) de ne the conditions for which it is enabled, (c) for each output place, de ne how to create tokens in the output places, (d) for each input place, de ne how to consume tokens in the output places. iii. for each lp-node lp,
(a) specify the logic constraint to be applied between inputs and outputs. iv. for each lt-node lt , (a) write down the logic dependencies between transitions allowing the propagation.
As a concrete example, we apply these actions on some of the components of the
LPPN in Fig. 3:
fluent(filled).
%%% p1, associated to c1
place(c1). % 1.a
initially(filled, c1). % 1.b
:- 2{terminates(e2, filled, c1, N); terminates(e1, filled, c1, N)}. % 1.c
%%% t1, associated to e1
transition(e1).
enabled(e1, N) :- holdsAt(filled, c1, N).
terminates(e1, filled, c1, N) :- firesAt(e1, N).
initiates(e1, filled, c2, N) :- firesAt(e1, N).
%% lp1
holdsAt(filled, c5, N) :- holdsAt(filled, c2, N).
%% lt1
firesAt(e3, N) :- firesAt(e1, N), enabled(e3, N).
% 2.a
% 2.b
% 2.c
% 2.d
% 3.a
% 4.a
Execution With the transformation steps given above, valid LPPNs can be
transformed into ASP programs. In particular, for the axioms presented here, these
programs can be solved the ASP engine clingo [
When we process the input LPPN by means of the denotational semantics, the input is transformed to an ASP program, and the solver intervenes fully to provide the possible execution paths. Instead, when we refer to the hybrid operational semantics, the solver intervenes only partially in the execution cycle, to entail the constraints implied by the declarative components of the net; the rest of the computational burden is on the module responsible for the Petri net execution. In this context, one might ask if we can observe some performances between these two alternative modes of analysis/execution. 7 Available at http://github.com/s1l3n0/pypneu. serial 1 EC 0.1 BF+BT 0.2
51 EC 352.4 BF+BT 11.0 forking 1 EC 0.1 BF+BT 0.4
6 EC 19.6 BF+BT 55.3
At the moment, we have only evaluated a propositional version of LPPN, and a limited series of structures, namely compositions of minimal serial elements (a transition with an input and output places) or minimal forking elements (a place with two output transitions). In order to implement the procedural component of the operational semantics, the current Petri Net analysis module builds upon a simple brute force (BF) execution algorithm, and depth- rst search with backtracking (BT) to cover all the possible execution paths.
Table 1 summarises the performances of 10 executions of di erent network con gurations.8 Results are also illustrated on Fig. 4. The data essentially conrms our hypothesis: the analysis based on the operational semantics (BF+BT) clearly outperforms and scales excellently for the serial con gurations, while that based on the denotational semantics (EC) scales poorly in this con guration. For the forking con gurations, BF+BT is evidently slower in absolute terms. Intuitively this is due to the e cient search and pruning capabilities of ASP. Unlike clingo, the Python code of the Petri net executor/analyzer is not optimised; on the contrary, for many aspects this represents a lower-bound on the possible implementation choices. Nevertheless, if we consider execution times in logarithmic scale, we observe that the two methods are essentially comparable in terms of tractability. 6
The paper presents an empirical experiment with LPPNs, a logic
programmingbased extension to Petri Nets. LPPNs were introduced with a practical goal
8 The tests were run on a MacBook Pro (2018) provided with a 2.2 GHz 6-core
processor Intel Code i7 and 16Gb RAM DDR4.
in mind: a visual modelling notation relatively simple for non-experts, that
could handle explicit declarative knowledge, and that could model causation
and other procedural aspects [
Here the focus has been put on its computational properties, showing that maintaining the two levels separated can bring better performances. The declarative dimension allows to treat at higher abstraction phenomena for which there is a viable speci cation at outcome level. The procedural dimension works better for processes that can be directly executed.
Future developments concern the extension of this work to a wider range of
experiments, rst considering mixed networks (of declarative, procedural
components) with mixed con gurations (serial compositions, forks, joins, etc.) and
then passing to the extended LPPN notation accounting for predicates. The
actual impact on real models should be evaluated as well: scenarios describing
cases have very few forks, they rather function as orchestrated (i.e. directed
from the scenario) scripts (procedural models distributed amongst actors).
Consequently, applications that require the use of scenarios (e.g. for interpretation,
model-based diagnosis, conformance checking, etc.) may take advantage of the
hybrid operational semantics. The computational improvement may be further
extended considering existing proposals in the literature. For instance, execution
algorithms alternative to brute execution [
Further, these results should be confronted with existing techniques for
handling temporal reasoning and causality, e.g. the already cited Action languages
[