# NeReF: Neural Refractive Field for Fluid Surface Reconstruction and Implicit
Representation

Ziyu Wang1
Wei Yang2
Junming Cao3
Lan Xu1
Junqing Yu2
Jingyi Yu1
1ShanghaiTech University  2Huazhong University of Science and Technology
3Shanghai Advanced Research Institute

###### Abstract

Existing neural reconstruction schemes such as Neural Radiance Field (NeRF)
are largely focused on modeling opaque objects. We present a novel neural
refractive field (NeReF) to recover wavefront of transparent fluids by
simultaneously estimating the surface position and normal of the fluid front.
Unlike prior arts that treat the reconstruction target as a single layer of
the surface, NeReF is specifically formulated to recover a volumetric normal
field with its corresponding density field. A query ray will be refracted by
NeReF according to its accumulated refractive point and normal, and we employ
the correspondences and uniqueness of refracted ray for NeReF optimization. We
show NeReF, as a global optimization scheme, can more robustly tackle
refraction distortions detrimental to traditional methods for correspondence
matching. Furthermore, the continuous NeReF representation of wavefront
enables view synthesis as well as normal integration. We validate our approach
on both synthetic and real data and show it is particularly suitable for
sparse multi-view acquisition. We hence build a small light field array and
experiment on various surface shapes to demonstrate high fidelity NeReF
reconstruction.

##  1 Introduction

Existing neural reconstruction schemes such as Neural Radiance Field (NeRF)
have shown its great power for scene representation and reconstruction.
However, NeRF and its successors largely focus on modeling opaque objects. In
contrast, modeling and reconstruction of refractive surfaces from photographs
have great importance for applications ranging from fluid physics analysis,
environmental monitoring to computer graphics. Refractive surfaces poses
exceptional challenges for NeRF representation as a light ray only diverts
from its straight path when traversing the air-fluid interface and hence makes
the sampling and radiance representation of rays no longer applicable.

Figure 1: Our Neural Refractive Field (NeReF) is formuated to recover a
volumetric normal field with its corresponding density field. Despite the
explicit depth and normal representation can be derived from NeReF, we can
render refraction effect and synthesize novel views directly from NeReF.

A common non-intrusive approach for estimating the shape of fluids is to
analyze the distortions of a reference pattern placed under the fluid [23]. In
particular, many approaches rely on imposing additional assumptions, such as
pattern appearance, water height [22, 25, 27] and optics [14, 16, 38], while
others create dedicated imaging/optics systems (e.g., camera array [10],
Bokode [38] and light field probe [34]) for acquiring fluid structures. Morris
et al. [22] introduce a novel refractive disparity for water surface recovery
using “stereo matching”. Qian et al. [25] use a camera array to estimate both
water surface and the underwater scene through exploiting the surface normal
consistence. Xiong and Heidrich [37] propose a novel differentiable framework
to reconstruct the 3D shape of underwater environments from a single,
stationary camera placed above the water. Notably, Thapa et al. [31] proposes
learning-based single-image approach with recurrent layers modeling spatio-
temporally consistence to recover dynamic fluid surfaces.

Existing approaches unanimously model the air-fluid interface as one layer of
geometry surface, which usually is explicitly represented by depth and normal
maps. Re-rendering of the refraction effect from depth and normal requires ray
tracing with hit point testing and two-bounce recursion. In this paper, we
propose a Neural Refractive Field (NeReF) to implicitly represent a fluid
surface, by taking the advantage of the recent success in neural implicit
scene representation. Our work is inspired by the Neural Radiance Field
(NeRF). More specifically, we use a fully-connected deep network to represent
the fluid surface, whose input is a 3D coordinate and outputs the volume
density and normal at the coordinate. We can perform re-rendering of
refraction effects directly from the implicit representation by integrating
normal along a target ray and deflecting it according to Snell’s law. Explicit
representations, such as depth and normal, can still be recovered effectively
via volume integration (Fig. 1). In contrast to supervised approaches [38],
NeReF optimization is performed in a per-scene manner and hence avoids the
lack of real dataset problem. Moreover, NeReF models a continuous function and
generates results at resolutions on demand. And NeReF model is relatively
smaller (about 4MB), the advantage expands as the desired resolution
increases. View synthesis from NeReF is easier compared to ray tracing. To
evaluate our proposition, we construct a multi-camera system similar to [26]
and capture a known pattern under dynamic fluid surface. We use the optical
flow [23] technique to obtain the groundtruth point-ray correspondences for
NeReF optimization. Experiment results show our training free approach can
recover the fluid surface with high fidelity. Our system setup is shown in
Fig. 4.

Compared to the original NeRF which models radiance along rays, we demonstrate
that the geometric information (normal of refractive surface) of the ray can
also be implicitly encoded in a neural field.

##  2 Related Work

Our work is closely related to researches in fluid surface reconstruction and
neural scene representation.

Image based Fluid Surface Reconstruction Shape from distortion analyzes the
distortions in images of patterns placed under water, and it is the most
common technique used for image based fluid reconstruction initiated by
Murase’s pioneering work [23]. The following shape-from-distortion methods can
be categorized into single-view based methods or multi-view based methods.
Approaches that adopt a single viewpoint setup usually assume additional
surface constraints, such as planarity [1, 5, 12] and integrability [34, 38],
to tackle the depth normal ambiguity. Notably, Tian and Narasimhan [32]
develop a data-driven iterative algorithm to rectify the water distortion and
recover water surface through spatial integration. Shan et al. [27] estimate
the surface height map from refraction images with global optimization. Xiong
and Heidrich [37] propose a novel differentiable framework to reconstruct the
3D shape of underwater environments from a single, stationary camera placed
above the water in the wild environment. In contrast, multi-view based
approaches rely on dedicately designed imaging/optic systems. Ye [38] exploit
Bokode - a computational optical device that emulates a pinhole projector - to
capture ray-ray correspondences, which can be used to directly recover the
surface normals. Morris et al.[22] extend the traditional multi-view
triangulation to be appropriate for refractive scenes, and build up a stereo
setup for water surface recovery. More recently, a learning-based single-image
approach has recently been presented for recovering dynamic fluid surfaces
[38]. Our capturing system setup is mainly similar to that of Qian et al.[25],
which creates a 3x3 camera array and use optical flow technique to recover
under water object(Fig. 2). However, like other approaches, it models the air-
fluid interface as depth and normal maps. In contrast, We propose to
implicitly encode the fluid surface into a fully connected neural network.

There is another line of works which aim to recover transparent objects, such
as gas flow [2], which we recommend to read for extra information.

Neural Radiance Field The remarkable work of Neural Radiance Field is a
milestone in novel view synthesis area. Before Mildenhall et at [21] raise the
idea of NeRF, several methods are proposed to predict photo-realistic novel
views of scenes base on dense sampling views. Theses methods can be divided
into two classes. One class of methods use mesh-based representations of
scenes with diffuse [33] or view-dependent [35, 9, 4] appearance, optimized by
differentiable rasetizers [7, 13, 18, 19] or pathtracers [24, 17]. Another
class of methods use volumetric representations to address this task. NeRF
combines the implict representation with volumetric rendering to achieve
compelling novel view synthesis with rich view-dependent effects. As the
headstone of many following works, including ours, NeRF uses the weights of a
multilayer perceptron(MLP) to represent a scene as a continuous volumetric
field of particles that block and emit light. It takes single continuous 5D
coordinates (spatial location $(x,y,z)$ and view direction $(\theta,\phi))$ as
input and outputs the volume density $\sigma$ and view-dependent color $c$.

Based on the pipeline of NeRF, several extended works have been proposed.
Ricardo et al [20] present an approach to enable the NeRF capable of modeling
uncontrolled images from unstructured photo collections with learning a per-
image latent embedding apperance variations and decomposing scenes into image-
dependent components. In Chen et al’s [6] work, the MVSNeRF is a deep neural
network that is able of utilizing three nearby input views via fast network
inference to reconstruct radiance fields. Jonathan et al [3] combine the mip-
map approach and NeRF together, simultaneously improve the original positional
encoding into an integrated positional encoding, which represent the volume
covered by each conical frustum, ending up with mip-NeRF which reduces
aliasing and improves NeRF’s ability to represent fine details. In Alex Yu et
al [39]’s PlenOctreees for real-time rendering of Neural radiance fields,
spherical harmonics are applied as the base of a representation of view-
dependent colors. Besides, PlenOctree is applied to store density and SH
coefficients modelling view-dependent appearance at each leaf. With these two
measures, this method can render images at more than 150FPS, which is
thousands times faster than the conventional method.

Neural Scene Representation Scene representation is a process that interprets
the visual data into a feature representation. By providing the aimed pose and
latent code [28] or alternatively transform views directly in the latent
space[36], novel view images can be rendered. Generative Query Network(GQN)
[11] provides framework within which machine learning scenes using their own
sensors. However, this framework has the limitation of being oblivious to the
3D structure. Voxel grid representations and graph neural networks are the
method that capture 3D structures. Vincent Sitzmann et al [29] propose a
continuous 3D-structure-aware neural scene representation network, which
trained from 2D images and their camera poses and encodes both geometry and
appearance. Following their previous work, Sitzmann propose the light field
network. This neural network represents the light field of a 3D scene
implicitly, which can be used to extract depth maps from 360-degree light
fields.

##  3 Neural Refractive Field

Figure 2: The overview of our fluid surface reconstruction approach based on
NeReF. Specifically, given multi-view inputs of fluid surface, we first
calculate the optical flow w.r.t. the patter without water. Then we train
NeReF with input images and it can produce depth and normal via volumetric
rendering. Then the loss is computed between recovered depth normal and
optical flow with refraction physics.

The core at our fluid surface reconstruction approach is as a neural
refraction field (NeReF), which retains the continuous scene representation
ability of NeRF. Before proceeding, let’s briefly review NeRF for easier
explanation. NeRF represents a scene using a fully-connected deep network,
whose input is a spatial location and viewing direction and output is the
volume density and view-dependent emitted radiance. A novel image view is
synthesized by sampling coordinates along camera rays and use volume rendering
techniques to project the output colors and densities into an image. In this
paper, we use the same scheme but adapt the NeRF for generating a normal value
at each spatial location.

Figure 3: The pipeline of our fluid surface recontruction method from NeReF. A
sample point on input ray goes through a MLP network to predict the density
and normal. The depth and normal can be explicitly rendered from NeReF and we
use a correspondence and depth normal consistency loss to optimize NeReF.

Specifically, we represent the continuous fluid surface as an implicit
function $\mathcal{F}$, which is approximated by a Multi-Layer Perception
(MLP). It takes a 3D location $(x,y,z)$ as input, and outputs the surface
normal $\mathbf{n}$ along with the volume density $\sigma$.

$\mathcal{F}:(x,y,z)\rightarrow(\sigma,\mathbf{n})$ (1)

Note that although this modification is relatively small, the underlying
hypothesis is very different. Our NeReF encodes the refractive surface normals
which deflect the rays spatially, in contrast NeRF models rays’ radiance which
is in another dimension of spatial domain.

###  3.1 Depth and Normal from Volume Accumulation

From NeReF, depth and normal are accumulated along the camera ray.
Specifically, given $k$ sample points along a camera ray
$\mathbf{r}=\mathbf{o}+\lambda\mathbf{d}$ where $\mathbf{o}$ is the origin of
the ray and $\mathbf{d}$ is the ray direction, with each sample point
determined by parameter $\lambda_{i},i\in\\{1,...,k\\}$. We query the sampling
point’s volume density $\sigma_{i}$ and normal $\mathbf{n}_{i}$. Then, we
calculate the surface normal $\mathbf{N}(r_{k})$ and depth $D(r_{k})$ of the
last sampling point $\lambda_{k}$ as:

$\begin{split}\mathbf{N}(\mathbf{r}_{k})=\sum^{k}_{i=1}\tau_{i}[1-\exp(-\sigma_{i}\delta_{i})]\mathbf{n_{i}}\\\
D(\mathbf{r}_{k})=\sum^{k}_{i=1}\tau_{i}[1-\exp(-\sigma_{i}\delta_{i})]\sigma_{i}\end{split}$
(2)

where $\tau_{i}=\exp\left(-\sum_{j=1}^{i-1}\sigma_{j}\delta_{j}\right)$, and
$\delta_{i}=\lambda_{i+1}-\lambda_{i}$ denotes the distance between two
adjacent samples along the ray. Then, the coordinate of 3D point that
$\mathbf{r}$ intersects the fluid surface is
$\mathbf{p}_{s}=\mathbf{o}+D(\mathbf{r}_{k})\mathbf{d}$

###  3.2 Refraction Execution

The implicit fluid representation should also obey the Snell’s Law when a ray
traverse the refractive surface. The refraction process follows Snell’s law,
i.e., $n_{1}\sin\theta_{1}=n_{2}\sin\theta_{2}$, where $n_{1},n_{2}$ and
$\theta_{1},\theta_{2}$ are the refraction indexes and incident and refracted
ray angles respectively.

For each camera ray $\mathbf{r}$, we calculate the refracted ray
$\mathbf{r}^{\prime}=\mathbf{p}_{s}+\lambda\mathbf{d}^{\prime}$ using the
Snell’s law in vector form, as:

$\mathbf{d}^{\prime}=\frac{s\cdot\mathbf{d}+(sa-b)\mathbf{N}(\mathbf{r})}{\|s\cdot\mathbf{d}+(sa-b)\mathbf{N}(\mathbf{r})\|_{2}}$
(3)

where

$\left\\{\begin{array}[]{lr}s=n_{1}/n_{2},&\\\
a=-\mathbf{N}(\mathbf{r})\cdot\mathbf{d_{c}},&\\\
b=\sqrt{1-s^{2}\left(1-(\mathbf{N}(\mathbf{r})\cdot\mathbf{d})^{2}\right)}\end{array}\right.$
(4)

In our case, $n_{1}$ and $n_{2}$ are the refractive indexes of air and water,
respectively.

##  4 Fluid Surface Reconstruction with NeReF

We represent the fluid surface implicitly with NeReF. One remaining problem is
how to train the network. Previous section describes how to refract a ray
using NeReF, in our implementation, we assume the camera ray refracts once
when it hits the fluid surface, i.e.,
$\mathbf{N}(\mathbf{r})=\mathbf{N}(\mathbf{r}_{k})$ for $k\to\infty$, but
remember this assumption is not required for our NeReF but only for the easy
analysis of the fluid surface reconstruction problem.

We can use the consistency between the refracted rays to optimize the network,
but need the ground truth refracted rays. Hence we follow the scheme of
previous approaches and place a reference pattern under the water. We first
capture images of the pattern without water and then pour the water in. Then
we can use the positional differences of corresponding intersection points on
pattern between the refracted rays and un-refracted rays and use it a loss for
NeReF optimization. The process is visualized in Fig. 3.

###  4.1 Problem Formation

We set the $x-y$ plane of coordinate system to be aligned with the reference
pattern, and $z$ direction is up and perpendicular to the pattern plane. Then
normal of the reference plane is $\mathbf{n}_{\pi}=[0,0,1]$. For a refracted
ray $\mathbf{r^{\prime}}(\lambda)=\mathbf{p}_{s}+\lambda\mathbf{d}^{\prime}$,
we can obtain the intersection point $\mathbf{q}^{\prime}$ with the reference
plane from ray-plane intersection:

$\lambda_{\mathbf{q^{\prime}}}=\frac{-\mathbf{p}_{s}\cdot\mathbf{n}_{\pi}}{\mathbf{d}^{\prime}\cdot\mathbf{n}_{\pi}}$
(5)

where $\cdot$ denotes the dot product. Similarly, we can obtain the
intersection point $\mathbf{q}$ of the ray without refraction from
$\lambda_{\mathbf{q}}$. Then our aim is to optimize the NeReF network from
$\mathbf{q}$ and $\mathbf{q}^{\prime}$.

However, there is still one remaining problem that we don’t know how to
correspond $\mathbf{q}$ and $\mathbf{q}^{\prime}$. Notice $\mathbf{p}$ and
$\mathbf{p}^{\prime}$ are projection points on the image plane of rays
$\mathbf{r}$ and $\mathbf{r}^{\prime}$. So the ray $\mathbf{r}$ that before
refraction can be directly obtained from camera parameters and pixel location
$\mathbf{q}$. Then we use the optical flow [30] technique to obtain a dense
warp field $\mathcal{W}$ from the distorted frame $I^{\prime}$ to reference
frame $I$, presumably we obtain the shift of $\mathbf{q}^{\prime}$ as:

$I(\mathbf{q}_{gt})=I^{\prime}(\mathbf{q}^{\prime}+d_{q})$ (6)

We set $\mathbf{q}_{gt}$ as our ground truth point for the refracted ray
$\mathbf{r}^{\prime}$ of $\mathbf{r}$. Then we refract $\mathbf{r}$ using
NeReF network during training and produce a $\mathbf{q_{\mathcal{F}}}$. We
define our correspondence loss as the L1 smoothed difference between
$\mathbf{q}_{gt}$ and $\mathbf{q_{\mathcal{F}}}$ as:

$\mathcal{L}_{corr}=\mathcal{S}^{1}(\|\mathbf{q_{\mathcal{F}}}-\mathbf{q}_{gt}\|_{2})$
(7)

where $\mathcal{S}^{1}$ denotes the L1 smooth operatoer.

###  4.2 Depth Smoothness

In practice, we notice depth tends to contain more noise compared to normal.
While according to fluid dynamics, depth should be very smooth due to physic
constraints. Hence we use a depth smoothness loss:

$\mathcal{L}_{ds}(D)=\frac{1}{M}\sum_{\mathbf{r}}\mathcal{S}^{1}(|\frac{\partial
D(\mathbf{r})}{\partial x}|+|\frac{\partial D(\mathbf{r})}{\partial y}|)$ (8)

Finally, our total loss then is the weighted combination of previous losses
as:

$\mathcal{L}_{tol}=\mathcal{L}_{corr}+\lambda_{ds}\mathcal{L}_{ds}$ (9)

Specifically, we set $\lambda_{ds}=0.15$ in our implementation.

##  5 Implementation Details

In our implementation, the NeReF consists of 8 fully connected layers and each
layer has 256 channels. The network takes location as input and generates
density $\sigma$. Then we use another 3 layers to regress normal from
$\sigma$. Hence the total size of our NeReF is about 4MB.

Training Details. We train our models using Adam optimizer with a learning
rate 4E-4 which decays 5E-5 per $1000$ iterations during training. Besides, we
sample 2048 camera rays for each mini-batch and sample 96 and 192 points from
near to far following the hierarchical sampling strategy. We optimize all our
networks on a PC with a single Nvidia GeForce RTX3090 GPU for 10 epochs. The
training time is about 2 hours.

Figure 4: The real fluid surface capture system which consists of 10 Z Cam E2,
a water tank and a pattern under the water. We reserve one camera specifically
for the evaluation purpose. On the right shows example real images captured.

System Setup. To validate the proposition of our NeReF, we construct a fluid
capture system consists of a water tank, a pattern underwater and a 10 camera
array. The water tank is with size 12 inches for wave simulation. The
industrial cameras we use is Z Cam E2 and we place all cameras on on top to
record videos of the water. We calibrate the intrinsics and extrinsics of the
cameras, and remove lens distortion using OpenCV [15]. We use 9 cameras for
NeReF training and the remaining one for evaluation and testing.

Figure 5: Example fluid surfaces from synthetic data generated by Blender
reconstructed by NeReF. From left to right are recovered normal map, normal
error, depth visualized as point cloud, and depth error map. The results
exhibit very small error and prove the effectiveness of our method.

##  6 Experiment

We first evaluate the fluid surface reconstruction approach based on our
NeReF, for synthetic fluid data generated by Blender [8]. We exploit the fluid
physics simulation ability of Blender and set up a scene that contains 25
cameras and water with size 2 x 1 x 4. We place a binary planar pattern
beneath the water, and then use wave modifier to simulate the shallow water
equation, Grestner’s equation, and Gaussian equation effects. We generate 4
sequences and each sequence contains 90 images. We place 25 pinhole cameras on
top of the fluid to observe the pattern distortions under various wave
functions.

We obtain a dense warp field using the optical flow [30] technique. Then, we
train our NeReF using 9 cameras as describe above and render the depth, normal
from NeReF using volumetric integration approach. We compute the relative
error, i.e., the error to ground truth ratio, for the depth error and use the
L2 norm of the difference between recovered and ground truth normal as the
depth and normal error respectively. The recovered normal is smooth and the
recovered point cloud is very accurate. We can see errors at most parts of the
normal and depth are small, only normal at the peaks of ripple waves show
relatively large errors. This is reasonable as the normal changes dramatically
in that region. Notice in Fig. 5, the scale of the error map is very small,
i.e., $0.1$, and some normal error in row 3 is just relatively larger. The
synthetic experiments demonstrate that our proposed NeReF works accurately for
fluid surface reconstruction.

###  6.1 Quantitative Evaluation.

To quantitatively evaluate our method, we compute the PSNR, LPIPS and SSIM
metrics on real data. Recall that we mounted 10 cameras on top of the water
tank for capturing the fluid dynamics. However, only 9 of them are used for
NeReF training and we use the remaining one for testing. Specifically, after
the NeReF is optimized, we synthesize a new view image by setting the sampling
camera to be exactly the same with the testing camera location. We compare the
synthesized image with the camera image in terms of PSNR, LPIPS and SSIM
metrics and the result is shown in Tab. 1. We also include the metrics
reported by the original NeRF and for references. We have tried our best to
find an alternative fluid surface reconstruction method to compare ours with.
We can only Ding’11 [10] that have the same multi-camera setup with available
code. Hence we use Ding’11 approach to recover the depth and normal, and then
generate the view and testing camera using ray tracking and report the metrics
in Tab. 1 too.

| PSNR | LPIPS | SSIM
---|---|---|---
Ding’11 | 25.110 | 0.062 | 0.878
NeRF | 21.560 | 0.217 | 0.684
Ours | 28.926 | 0.033 | 0.942

Table 1: Comparison of our NeReF with the original NeRF and Ding’11 [10] in
term of recover accuracy. PSNR, LPIPS and SSIM values of our method and the
original NeRF on the real fluid sequence. Figure 6: The re-rendering results
directly from NeReF (not through ray tracing using depth and normal) on
synthetic data compared with other methods.

As we can see the NeReF show good metrics and it means that the synthesized
data matches well with the testing camera.

###  6.2 Ablation Study

Here we analysis how several key factors in the system would affect our
system:

Tolerance of flow error

Since optical flow provides the ground truth for our NeReF training, we first
evaluate how errors in optical flow affect the final performance. From our
synthetic data in above section, we have the ground truth optical flow. Then
we add random noise at different amplitude levels, train and test the NeReF
model and then use the optimized NeReF model for depth and normal recovery
tasks.

Figure 7: We study how noises in optical flow affect the performance of NeReF.
We gradually increase the noise level and train the NeReF for depth and normal
recovery, and calculate the error with ground truth.

Figure 7 shows the depth inaccuracy, which is calculated by error to ground
truth depth ratio, and the normal error mean. As we can see, the depth
inaccuracy and normal error mean increase when we add larger noise to optical
flow. But it also shows that our NeReF is relatively robust to noise in
optical flow as the error curve exhibit a linear increasing tendency instead
of a exponential increasing curve.

Camera Number Evaluation

The number of cameras is another important term that may affect the
performance significantly. We tested the camera numbers from 9, 7, 5 to 3. And
we train NeReF with with the corresponding camera views. After training, we
synthesize images at testing view points with the trained model and compare
with the ground truth depth and normal. We use the average depth and normal
error of all testing views. The result is shown in Tab. 2, as we can see as as
the number of cameras decreases, the error in Reconstruction becomes larger,
which is as predicted.

Number of cams. | Recovered Depth | Recovered Normal
---|---|---
RMSE (meters) | Angle Diff. (deg.)
9 | 0.02252 | 0.28477
7 | 0.03193 | 0.34128
5 | 0.04540 | 0.43536
3 | 0.05683 | 0.84187

Table 2: Ablation study on number of cameras. RMSE of depth and Average Angle
Difference of normal increases as the number of cameras descreases.

###  6.3 Refraction and View Synthesis with NeReF

One important property of NeRF is its ability of synthesizing photo-realitic
novel views. This ability comes from the representation of density, and novel
view is synthesize via volumetric integration of density and produces depth.
Similarly in our NeReF, we can integrate the volume to obtain depth and
normal. With the depth and normal, we can directly apply Snell’s law to find
the refracted ray and hence find where the ray hits after refraction. As such,
we can perform background change and novel view synthesis from the NeReF.

We first compare our NeReF with the original NeRF and ray tacing through depth
and normal generated by [10]. The comparison is shown in Fig. 6. We can see
original NeRF performs very poorly as the ray geometry are wrong. Moreover,
result from ray tracing [10] contains artifacts as ray tracing can only
performed at a certain resolution. While the synthesis result from our NeReF
is the most close to ground truth.

Then we compare the novel view synthesis result on real fluid data the fluid
data. Fig. 8 exhibits that results by ray tracing from Ding’11 [10] depth and
normal usually contain minor artifacts, the result from original NeRF is
unusable, and results from our approach are very close to the ground truth.
The rendered binary pattern is much more clearer and it deforms in the same
way as the real image.

In Fig. 9, we show the recovered depth and normal for the frame captured in
Fig. 8. And we re-render use NeReF’s volume integration with a new pattern at
different viewing points. Notice how distortions are presented differently in
each image due to viewing point change.

Figure 8: The re-rendering results directly from NeReF (no depth or normal
explicitly involved) compared with the original NeRF, ray tracing from Ding’11
depth and normal, the ground truth at the testing view. Figure 9: Depth and
normal from NeReF optimized on our real captured data. We also show 3 re-
rendering image from NeReF with a changed pattern at different viewpoints,
notice how distortions are presented at different views.

##  7 Discussion

In this paper, we propose a neural scene representation for refractive fluid
surfaces, called the Neural Refractive Field or NeReF. Specifically, we
represent the fluid surface as a fully-connected deep network, which takes 3D
coordinates as input and output the volume density and normal. We can render
the refraction effect directly from the implicit representation.

We only train and test the NeReF with fluid surface in a water tank. The
surface is then rather flat and we assume one time of refraction. This
assumption may not hold for water in flow or more complicate fluid surface.
Hence, in the future, we plan to employ our method for complicated refractive
shape recovery. Moreover, our adaption approach has removed the view dependent
radiance from NeRF. Hence the render results from NeReF is a constant color
from pattern no matter what direction the target view is. We plan to add the
view dependent radiance to NeReF and make it be able to synthesize specular
highlights.

## References

  * [1] Yuta Asano, Yinqiang Zheng, Ko Nishino, and Imari Sato.  Shape from water: Bispectral light absorption for depth recovery.  In European Conference on Computer Vision, pages 635–649. Springer, 2016.
  * [2] Bradley Atcheson, Ivo Ihrke, Wolfgang Heidrich, Art Tevs, Derek Bradley, Marcus Magnor, and Hans-Peter Seidel.  Time-resolved 3d capture of non-stationary gas flows.  ACM transactions on graphics (TOG), 27(5):1–9, 2008.
  * [3] Jonathan T. Barron, Ben Mildenhall, Matthew Tancik, Peter Hedman, Ricardo Martin-Brualla, and Pratul P. Srinivasan.  Mip-nerf: A multiscale representation for anti-aliasing neural radiance fields.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 5855–5864, October 2021.
  * [4] Chris Buehler, Michael Bosse, Leonard McMillan, Steven Gortler, and Michael Cohen.  Unstructured lumigraph rendering.  In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, pages 425–432, 2001.
  * [5] Yao-Jen Chang and Tsuhan Chen.  Multi-view 3d reconstruction for scenes under the refractive plane with known vertical direction.  In 2011 International Conference on Computer Vision, pages 351–358. IEEE, 2011.
  * [6] Anpei Chen, Zexiang Xu, Fuqiang Zhao, Xiaoshuai Zhang, Fanbo Xiang, Jingyi Yu, and Hao Su.  Mvsnerf: Fast generalizable radiance field reconstruction from multi-view stereo.  arXiv preprint arXiv:2103.15595, 2021.
  * [7] Wenzheng Chen, Huan Ling, Jun Gao, Edward Smith, Jaakko Lehtinen, Alec Jacobson, and Sanja Fidler.  Learning to predict 3d objects with an interpolation-based differentiable renderer.  Advances in Neural Information Processing Systems, 32:9609–9619, 2019.
  * [8] Blender Online Community.  Blender - a 3D modelling and rendering package.  Blender Foundation, Stichting Blender Foundation, Amsterdam, 2018.
  * [9] Paul E Debevec, Camillo J Taylor, and Jitendra Malik.  Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach.  In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pages 11–20, 1996.
  * [10] Yuanyuan Ding, Feng Li, Yu Ji, and Jingyi Yu.  Dynamic fluid surface acquisition using a camera array.  In 2011 International Conference on Computer Vision, pages 2478–2485. IEEE, 2011.
  * [11] SM Ali Eslami, Danilo Jimenez Rezende, Frederic Besse, Fabio Viola, Ari S Morcos, Marta Garnelo, Avraham Ruderman, Andrei A Rusu, Ivo Danihelka, Karol Gregor, et al.  Neural scene representation and rendering.  Science, 360(6394):1204–1210, 2018.
  * [12] Ricardo Ferreira, Joao P Costeira, and Joao A Santos.  Stereo reconstruction of a submerged scene.  In Iberian Conference on Pattern Recognition and Image Analysis, pages 102–109. Springer, 2005.
  * [13] Kyle Genova, Forrester Cole, Aaron Maschinot, Aaron Sarna, Daniel Vlasic, and William T Freeman.  Unsupervised training for 3d morphable model regression.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 8377–8386, 2018.
  * [14] Kai Han, Kwan-Yee K Wong, and Miaomiao Liu.  Dense reconstruction of transparent objects by altering incident light paths through refraction.  International Journal of Computer Vision, 126(5):460–475, 2018\.
  * [15] Itseez.  The OpenCV Reference Manual, 2.4.9.0 edition, April 2014.
  * [16] Yu Ji, Jinwei Ye, and Jingyi Yu.  Reconstructing gas flows using light-path approximation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2507–2514, 2013.
  * [17] Tzu-Mao Li, Miika Aittala, Frédo Durand, and Jaakko Lehtinen.  Differentiable monte carlo ray tracing through edge sampling.  ACM Transactions on Graphics (TOG), 37(6):1–11, 2018.
  * [18] Shichen Liu, Tianye Li, Weikai Chen, and Hao Li.  Soft rasterizer: A differentiable renderer for image-based 3d reasoning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7708–7717, 2019.
  * [19] Matthew M Loper and Michael J Black.  Opendr: An approximate differentiable renderer.  In European Conference on Computer Vision, pages 154–169. Springer, 2014.
  * [20] Ricardo Martin-Brualla, Noha Radwan, Mehdi SM Sajjadi, Jonathan T Barron, Alexey Dosovitskiy, and Daniel Duckworth.  Nerf in the wild: Neural radiance fields for unconstrained photo collections.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7210–7219, 2021.
  * [21] Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng.  Nerf: Representing scenes as neural radiance fields for view synthesis.  In European conference on computer vision, pages 405–421. Springer, 2020.
  * [22] Nigel JW Morris and Kiriakos N Kutulakos.  Dynamic refraction stereo.  IEEE transactions on pattern analysis and machine intelligence, 33(8):1518–1531, 2011.
  * [23] H. Murase.  Surface shape reconstruction of an undulating transparent object.  In [1990] Proceedings Third International Conference on Computer Vision, pages 313–317, 1990.
  * [24] Merlin Nimier-David, Delio Vicini, Tizian Zeltner, and Wenzel Jakob.  Mitsuba 2: A retargetable forward and inverse renderer.  ACM Transactions on Graphics (TOG), 38(6):1–17, 2019.
  * [25] Yiming Qian, Minglun Gong, and Yee-Hong Yang.  Stereo-based 3d reconstruction of dynamic fluid surfaces by global optimization.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1269–1278, 2017.
  * [26] Yiming Qian, Yinqiang Zheng, Minglun Gong, and Yee-Hong Yang.  Simultaneous 3d reconstruction for water surface and underwater scene.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 754–770, 2018.
  * [27] Qi Shan, Sameer Agarwal, and Brian Curless.  Refractive height fields from single and multiple images.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 286–293. IEEE, 2012.
  * [28] Vincent Sitzmann, Justus Thies, Felix Heide, Matthias Nießner, Gordon Wetzstein, and Michael Zollhofer.  Deepvoxels: Learning persistent 3d feature embeddings.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2437–2446, 2019.
  * [29] Vincent Sitzmann, Michael Zollhöfer, and Gordon Wetzstein.  Scene representation networks: Continuous 3d-structure-aware neural scene representations.  arXiv preprint arXiv:1906.01618, 2019.
  * [30] Zachary Teed and Jia Deng.  Raft: Recurrent all-pairs field transforms for optical flow.  In European conference on computer vision, pages 402–419. Springer, 2020.
  * [31] Simron Thapa, Nianyi Li, and Jinwei Ye.  Dynamic fluid surface reconstruction using deep neural network.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 21–30, 2020.
  * [32] Yuandong Tian and Srinivasa G Narasimhan.  A globally optimal data-driven approach for image distortion estimation.  In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1277–1284. IEEE, 2010.
  * [33] Michael Waechter, Nils Moehrle, and Michael Goesele.  Let there be color! large-scale texturing of 3d reconstructions.  In European conference on computer vision, pages 836–850. Springer, 2014.
  * [34] Gordon Wetzstein, Ramesh Raskar, and Wolfgang Heidrich.  Hand-held schlieren photography with light field probes.  In 2011 IEEE International Conference on Computational Photography (ICCP), pages 1–8. IEEE, 2011.
  * [35] Daniel N Wood, Daniel I Azuma, Ken Aldinger, Brian Curless, Tom Duchamp, David H Salesin, and Werner Stuetzle.  Surface light fields for 3d photography.  In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 287–296, 2000.
  * [36] Daniel E Worrall, Stephan J Garbin, Daniyar Turmukhambetov, and Gabriel J Brostow.  Interpretable transformations with encoder-decoder networks.  In Proceedings of the IEEE International Conference on Computer Vision, pages 5726–5735, 2017.
  * [37] Jinhui Xiong and Wolfgang Heidrich.  In-the-wild single camera 3d reconstruction through moving water surfaces.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 12558–12567, 2021.
  * [38] Jinwei Ye, Yu Ji, Feng Li, and Jingyi Yu.  Angular domain reconstruction of dynamic 3d fluid surfaces.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 310–317. IEEE, 2012.
  * [39] Alex Yu, Ruilong Li, Matthew Tancik, Hao Li, Ren Ng, and Angjoo Kanazawa.  Plenoctrees for real-time rendering of neural radiance fields.  arXiv preprint arXiv:2103.14024, 2021.


# On probabilistic stable event structures

Nargess Ghahremani and Julian Bradfield  Laboratory for Foundations of
Computer Science, University of Edinburgh,
10 Crichton St, Edinburgh, EH8 9AB, U.K.
<EMAIL_ADDRESS>
##  1 Introduction

Verification has been a core concern of theoretical computer science for
several decades. As most real systems are in some sense distributed or
concurrent, one has to decide how to model concurrency. Broadly, there are two
schools: the interleaving approach imposes a global ‘clock’ on the system, and
says that independent concurrent events occur in some order, but that order is
arbitrary – encapsulated by the CCS interleaving law $a|b=a.b+b.a$. ‘True
concurrency’, on the other hand, represents concurrency explicitly in the
semantics of the system, as exemplified by Petri nets. There are many
arguments about the merits, ranging from the practical – e.g. that true
concurrent models avoid the exponential state explosion arising from arbitrary
interleaving – to the philosophical – one should understand concurrency in its
own right.

Another extension of classical computation is probability, whether used to
model genuine randomness, or uncertainty. Probabilistic models have in the
last two or three decades also been the subject of intensive research, and by
now there are many widely used tools for practical verification of
probabilistic systems, based on a range of different theoretical models. A
small selection of established models and systems might be [16, 15, 22, 14,
26, 18, 5, 3]. Such work adopts the ‘interleaving’ approach to concurrency –
that is, from the true concurrency proponent’s point of view, it ignores
concurrency.

The topic of this paper is the combination of probability with true
concurrency. As well as the core interleaving vs. true concurrency
distinction, there is another crucial difference between the two in the
probabilistic framework: in probability, one cares about the probabilistic
(in)dependence of events, and in true concurrency this relation is (at least)
correlated with, and ideally derived from, the concurrency relation. To put it
another way, temporal stochastic processes and models capturing concurrency
through nondeterminism such as [12, 6, 16, 17, 7] have a global state
corresponding to a global time. In a distributed system, however, this is
neither feasible nor natural. Thus, in true concurrency approaches there is no
notion of global time or state, but rather local ones. In other words, the
local components have their own local states and act in their own local time
until they communicate together. This results in a highly desirable match
between concurrency and probability, so that concurrent choices can be made
probabilistically independent.

There is some work, quite recently, on probabilistic true concurrency models
[23, 9, 20, 21, 4, 1, 2], but this is still at the foundational semantic
stage, and there are very few no true concurrent probabilistic temporal logics
– a recent example in the setting of distributed Markov chains is in [10].

Therefore, in [8] the first author aimed to develop a probabilistic temporal
logic suitable for application to Petri nets, which are one of the best known
true concurrent models, even though often used with a forced interleaving
semantics. As part of this programme, it was necessary first to extend lower-
level models, which is the work reported here.

###  1.1 Related work

Event structures [24], and extensions thereof, are our basic model of
concurrency. While they are a very ‘low level’ model, unsuited for direct
modelling of systems, they model directly concurrency and causality –
causality being (roughly) the converse of concurrency.

To our knowledge, the first probabilistic model for event structures was given
in [13], which defines probabilistic extended bundle event structures. As with
the stable event structures we discuss later, these allow different possible
causes for an event, only one of which can be the cause in a run. However,
they capture choice by means of groups of events which are mutually in
conflict and enabled at the same time, called _clusters_. Clusters can be
determined statically, and maintain the concept of choice internal to the
system.

A domain theoretic view, closely related to the probabilistic powerdomains of
[11, 19], was taken by Varacca, Volzer and Winskel [21], who define continuous
valuations on the domain of configurations. They then define _non-leaking
valuations with independence_ on confusion-free event structures. These turn
out to coincide with distributed probabilities as defined by [1].

Randomised Petri nets along with their corresponding probabilistic branching
processes defined in [23] focus on free-choice conflicts only and therefore do
not deal with confusion.

Finally, the most recent probabilistic event structures defined by Winskel
[25] extend existing notions of probabilistic event structures in order to
make them suitable for dealing with certain interactions between strategies.

The main hurdle in defining a probabilistic concurrent system with partial
order semantics is to find units of choice so that concurrent units are
probabilistically independent. Abbes and Benveniste in [1] define distributed
probabilities taking _branching cells_ as units of choice and show that in
probabilistic event structures not only does concurrency match probabilistic
independence, but also that this cannot be achieved at a grain finer than that
of branching cells. Furthermore, they show how finite configurations can be
decomposed into branching cells dynamically, where maximal configurations of
the branching cells enforce all the conflicts within the cell to be resolved.
_Local probabilities_ are assigned to each branching cell and these can be
extended to a _limiting probability_ measure on the space of maximal
configurations. The only constraint required is that of _local finiteness_
which can be viewed as bounded confusion and which is defined later.

###  1.2 Summary

In this article, we first explain the motivation for studying probabilistic
stable event structures. Then, after the necessary preliminaries, we define
_conflict-driven_ stable event structures, a superclass of event structures
allowing enough ‘confusion’ to model Petri nets (the ultimate aim of this
work), but constrained enough to allow a manageable probabilistic semantics.
To extent the concepts of [1] to this setting, we need to constrain them to a
certain sub-class of _jump-free_ (stable) event structures. We then show that
probabilistic jump-free stable event structures can be defined analogously to
probabilistic event structures.

##  2 Motivation

As we said above, our original aim was probabilistic logic for Petri nets, and
this work forms part of the route to there. So before diving in to the
unfortunately but inevitably highly technical development of probabilistic
stable event structures, let us explain the key issues in the more widely
understood formalism of Petri nets.

Consider the following two safe nets:

$\bullet$$\bullet$$\bullet$$t_{1}$$t_{2}$$t_{3}$$t_{4}$$t_{a}$$t_{b}$$u_{1}$$u_{2}$$v$$\bullet$$\bullet$

The left net demonstrates several instances of confusion, where the occurrence
of one event changes the possibilities elsewhere in the net. Now suppose that
we add probabilities. There are several ways to do this, but they will all
boil down to assigning probabilities to the choices between say $t_{1}$ or
$t_{2}$, and $t_{2}$ or $t_{3}$, and so on. However, because of confusion, the
various choices are not independent. For example, whether a choice arises
between $t_{a}$ and $t_{b}$ depends on whether $t_{b}$ was enabled by $t_{1}$
or $t_{2}$. Worse, an event arbitrarily far away may be the source of such
confusion: the firing of $t_{4}$ disables $t_{3}$, thereby stopping it from
conflicting with $t_{2}$. Worse still, this confusion then propagates to
affect the choice between $t_{a}$ and $t_{b}$, which superficially have
nothing to do with each other. In the absence of independence, it is hard to
see how to give a useful probabilistic semantics that reflects concurrency.
Thus, it is equally hard to extend probabilistic temporal logics (making
statements such as ‘transition $t$ fires with probability ${}>0.5$ in all
futures’) to nets.

The right net is perhaps even more pathological: $u_{1}$ and $u_{2}$ can fire
away independently, but the malign presence of $v$ waiting to disable them
both at some time means that they cannot be treated as truly independent.

This problem, which more generally we might characterize as ‘the problem of
negative causality’, has been troubling the community for decades, and we have
not solved it. Instead we looked for ways to analyse differing levels of
confusion, so that at least we could define manageable classes of nets. In the
course of this, the first author [8] first developed a new notion of ‘compact
unfolding’ of Petri net, which allows some degree of backward conflict to be
maintained without being unfolded out. It turns out that just as standard net
unfoldings give rise to an event structure semantics for Petri nets, compact
unfoldings give rise to a stable event structure semantics. Hence we needed to
extend the existing work on probabilistic semantics from event structures to
stable event structures.

##  3 Preliminaries

Owing to the lengthy formal definitions needed for the work we build on, we
shall present most of the preliminaries in summary form, referring to [8] or
standard texts for formalities.

###  3.1 Event structures and their variants

The event structures of Winskel [24] model concurrency by describing
_consistency_ and _enabling_ relations between _events_. They are a low-level
model, as each event corresponds to an occurrence of a transition or action in
higher-level models such as Petri nets or process calculi. Thus, they are
suited to foundational investigations in concurrency theory.

For historical reasons, the terminology is a little confusing, and has also
changed during the development of the subject. Here we shall use _general
event structures_ for the original and most general formulation; _stable event
structures_ impose the restriction that an event has a unique set of causing
events; and plain _event structures_ are those generated by binary _causality_
and _conflict_ relations on events, rather than more general predicates. Owing
to our very frequent use of these long terms, we will abbreviate them.

###### Definition 1

A _general event structure ( ges)_ $\mathcal{E}$ is a set of _events_ $E$
equipped with a non-empty subset-closed _consistency predicate_
$Con\subseteq\wp_{\mathrm{fin}}(E)$ on finite sets of events, and an _enabling
relation_ ${\vdash}\subseteq Con\times E$, monotone in the first argument. A
_configuration_ of $\mathcal{E}$ is a (possibly infinite) subset $x\subseteq
E$ that is finitely consistent, and such that every $e\in x$ has a finite
enabling set in $x$. The set of all configurations of $\mathcal{E}$ is
represented by $\mathcal{V}(\mathcal{E})$ or $\mathcal{V}_{\mathcal{E}}$ or
$\mathcal{V}$ when no confusion arises.

###### Definition 2

Let $(P,\sqsubseteq)$ be a partial order. Then $S\subseteq P$ is _compatible_
(${S\uparrow}$) iff $\exists p\in P.\;\forall s\in S.\;s\sqsubseteq p$. A
subset is finitely compatible (${S\uparrow}^{\textit{fin}}$) iff $\forall
S_{0}\subseteq_{\textit{fin}}S.\;{S_{0}\uparrow}$.

The configurations $\mathcal{V}=\mathcal{V}(\mathcal{E})$ of $\mathcal{E}$
form a family of subsets of $E$ that is finite-complete
($\mathcal{A}\subseteq\mathcal{V}\;\&\;{\mathcal{A}\uparrow}^{\textit{fin}}\Rightarrow\bigcup\mathcal{A}\in\mathcal{V}$),
finitely based ($\forall u\in\mathcal{V}.\;\forall e\in u.\;\exists
v\in\mathcal{V}.\;(v\text{ is finite }\&\;e\in v\;\&\;v\subseteq u)$), and
coincidence-free ($\forall u\in\mathcal{V}.\;\forall e,e^{\prime}\in u.\;e\neq
e^{\prime}\Rightarrow(\exists v\in\mathcal{V}.\;v\subseteq u\;\&\;(e\in
v\Leftrightarrow e^{\prime}\notin v))$). It can be shown that given a family
$\mathcal{V}\subseteq 2^{E}$ that is finite-complete, finitely based and
coincidence-free, $\mathcal{V}$ is the set of configurations of the ges
$\mathcal{E}=(E,Con,\vdash)$ given by $x\in
Con\Leftrightarrow_{\textit{def}}x\text{ is finite }\&\;\exists
u\in\mathcal{V}.\;x\subseteq u$ and $x\vdash
e\Leftrightarrow_{\textit{def}}x\in Con\;\&\;\exists u\in\mathcal{V}.\;e\in
u\;\&\;u\subseteq x\cup\\{e\\}$.

General event structures are one of the most general classes of event
structures; they allow for an event to have different causes, which is a
desirable property. However, problems arise when dealing with configurations
in which an event does not have a unique cause, in that its different causes
can occur at the same time. Such configurations can be excluded by applying a
_stability_ constraint, leading to the definition of stable event structures.
It is worth noting that for stable event structures there is no global partial
order of causal dependency on events, but each configuration has its own local
partial order of causal dependency.

###### Definition 3

A _stable event structure ( ses)_, is an ges such that mutually consistent
enabling sets are closed under intersection, so that any set enabling $e$ has
a unique minimal enabling subset, the ‘causes’ of $e$.

Non-empty compatible configurations of an ses are closed under intersection,
and such a _stable family_ of configurations induces an ses.

Given a stable family $\mathcal{V}$ of configurations, and $e,e^{\prime}\in
u\in\mathcal{V}$ define $e\leq_{u}e^{\prime}$ if for all $v:\,\mathcal{V}\ni
v\subseteq u$ we have $e^{\prime}\in v$ implies $e\in v$ (i.e. $e$ is a
necessary member of the $u$-history of $e^{\prime}$). Let $\lceil e\rceil_{u}$
be the least configuration $v\subseteq u$ containing $e$ (the ‘causal history’
of $e$ in $u$).

An alternative approach to stability is to define $\leq$ in the structure as a
global partial order of causal dependency on events:

###### Definition 4

A _prime event structure ( pes)_ $\mathcal{E}$ on $E$ comprises $Con$ as
before, and a partial order $\leq$ on $E$ (the _causality relation_) such that
the down-closure $\lceil e\rceil$ of $e$ under $\leq$ is finite, singleton
events are consistent, $Con$ is closed under subsets and under adding causes
of events. The set of configurations of a pes is the set of $\leq$-down-closed
consistent configurations, and is a stable family of configurations for
$\mathcal{E}$ [24].

Thus a pes is itself a ses with the naturally induced enabling relation. Less
obviously, a ses can be translated into a pes by extending and renaming the
events, so that each event is augmented with the history of how it occurred in
a configuration. Then, even though the events and as such the configurations
are different, the domains of configurations of both event structures are
isomorphic as partial orders [24]. This translation is indeed right adjoint to
the embedding of pes in ses, in the categorical framework that Winskel sets
up.

Finally, generating the consistency relation from a binary conflict relation
gives

###### Definition 5

An _event structure ( es)_ $\mathcal{E}$ on $E$ comprises a causality relation
$\leq$ as above, and a binary, symmetric and irreflexive _conflict relation_
$\\#$ on $E$ which is is $\leq$-upwards-closed (i.e. events inherit the
conflicts of their causes).

A configuration of $\mathcal{E}$ is a $\leq$-downwards-closed and conflict-
free subset of $E$. Write $\lceil e\rceil$ as above, and $\lceil x\rceil$ for
$\bigcup_{e\in x}\lceil e\rceil$.

###  3.2 Probabilistic Event Structures

This subsection is a (severe) summarization of the concepts introduced by [1].
The abstract definition is conceptually fairly simple.

A _probability measure_ on a space $\Omega$ is a function from a suitable
collection (technically a $\sigma$-algebra) of subsets of $\Omega$ to $[0,1]$,
satisfying the appropriate behaviour for probabilities (the measure of a union
of disjoint sets is the sum of the measures).

Now consider an es, and let $\Omega$ be the space of its maximal
configurations (finite or infinite, perhaps uncountably infinite) where the
system has run to completion. There is a $\sigma$-algebra on $\Omega$
comprising the sets $\\{\omega\in\Omega:\omega\supseteq v\\}$ for each
configuration $v$ – that is, each set is a full subtree of the configuration
tree rooted at $v$. Call this set $S(v)$ (the _shadow_ of $v$). The intuition
is that the probability of $v$ is equal to the sum of the probabilities of all
the maximal configurations $\omega$ reachable from $v$ – except that not all
such configurations are probabilistically independent, so the usual
probability calculations for non-independent events have to be made.

###### Definition 6

A _probabilistic event structure ( pres)_ is a pair
$(\mathcal{E},\mathbb{P})$, where $\mathbb{P}$ is a _probability measure_ on
the space of maximal configurations of $\mathcal{E}$ with the $\sigma$-algebra
of shadows.

The _likelihood function_ on configurations of $\mathcal{E}$ is the function
$p(v)=\mathbb{P}(S(v))$.

This definition is very abstract, and hard to calculate with or implement via
a process calculus. Much of the work of [1] is in giving an alternative
operational presentation, which we now introduce via a long series of notions.
In the rest of this section, $\mathcal{E}=(E,{\leq},\\#)$ is an es,
$e,e^{\prime}$ etc. range over $E$, and $u,v$ etc. range over
$\mathcal{V}(\mathcal{E})$.

###### Definition 7

$P\subseteq E$ is a _prefix_ if $P=\lceil P\rceil$ (closed under causes). If
$F\subseteq E$, then
$(F,{\leq}{\mathord{\upharpoonright}}F,\\#{\mathord{\upharpoonright}}(F\times
F))$ is an es (which is a sub-es of $\mathcal{E}$). We use $F$ to also refer
to the sub-es induced by $F$, when no confusion arises.

Hence, configurations are conflict-free prefixes. $v$ is _maximal_ iff it is a
$\subseteq$-maximal configuration. We denote the maximal configurations of
$\mathcal{E}$ by $\Omega(\mathcal{E})$ or just $\Omega$.

The _future_ $\mathcal{E}^{v}=(E^{v},\leq^{v},\\#^{v})$ of $v$, where
$E^{v}=\\{e\notin v:\lceil e\rceil\cup v\in\mathcal{V}\\}$, is the es
generated by events that can happen after $v$. Given $u\in\mathcal{V}$ and
$v\in\mathcal{V}^{u}$, the _concatenation_ $u\oplus v$ is just $u\cup v$; and
given configurations $v\subseteq u$, the _subtraction_ $u\ominus v$ is just
$u\setminus v$.

In a probabilistic event structure, the probability reflects the notion of
choice which arises whenever a conflict is encountered for the first time.
Thus, we consider the ‘first-hand’ conflicts, i.e. conflicts which are not
inherited, as constituents of units of choice. Then we consider those prefixes
which contain all immediate conflicts, and maximal configurations within them,
which resolve all choices that can be made. The final step is to close under
concatenation to give a notion of ‘R-stopped configuration’, which provides a
probabilistically independent unit.

###### Definition 8

Events $e$ and $e^{\prime}$ are in _immediate conflict_ $e\\#_{\mu}e^{\prime}$
iff $\\#\cap(\lceil e\rceil\\!\times\\!\lceil
e^{\prime}\rceil)=\\{(e,e^{\prime})\\}$ (i.e. their conflict is not from
conflicting causes).

A prefix $B$ of $\mathcal{E}$ is a _stopping prefix_ if it is
$\\#_{\mu}\text{-closed}$. Given a set $X\subseteq E$, $X^{*}$ is the closure
of $X$ under $\\#_{\mu}$ and $\lceil\hbox{--}\rceil$ – it is the _minimal
stopping prefix_ containing $X$.

$v$ is _$B$ -stopped_ if $v$ is maximal in $\mathcal{V}(B)$; and $v$ is
_stopped_ if it is $v^{*}$-stopped.

$v$ is R-stopped if there is a sequence $\varnothing\subseteq
v_{1}\subseteq\dots\subseteq v_{n}\dots$ such that $v=\bigcup v_{n}$ and each
$v_{n+1}\ominus v_{n}$ is finite and stopped in $\mathcal{E}^{v_{n}}$.

The sequence is called a valid decomposition of $v$ and if $v=v_{N}$ for some
$N$, then $v$ is finite R-stopped. The set of $R$-stopped configurations is
written ${\mathcal{W}(\mathcal{E})}$.

Thus R-stopped configurations are the end of a sequence of steps, each of
which resolves all possible choices before it. It remains to decompose these
steps into their concurrent (i.e. independent) components.

###### Definition 9

$\mathcal{E}$ is pre-regular, if for every finite $v$, there are finitely many
events enabled by $v$.

$\mathcal{E}$ is locally finite if every $e\in E$ is in some finite stopping
prefix.

[1] theorem 3.12 shows that then all maximal configurations are $R$-stopped.
Henceforth all es are locally finite.

###### Definition 10

If $\mathcal{X}\subset\mathcal{V}$, write $\overline{\mathcal{X}}$ for the
subset of its finite configurations.

An initial stopping prefix is a minimal non-empty stopping prefix.

A _branching cell_ _enabled by_ a finite $R$-stopped $v$ is an initial
stopping prefix of $\mathcal{E}^{v}$. The set of such branching cells is
notated $\delta_{\mathcal{E}}(v)$.

It can be shown that $v$, with valid decomposition $(v_{n})$, has a _covering_
$\Delta_{\mathcal{E}}(v)$, a sequence $(c_{n})$ of branching cells such that
$v_{n}$ enables $c_{n+1}$ and $v_{n+1}\setminus v_{n}$ is maximal in
$c_{n+1}$. That is, $(c_{n})$ gives a sequence of maximal independent steps to
reach $v$.

The set of all branching cells of $\mathcal{E}$ is denoted by
$\mathcal{C}(\mathcal{E})$ and the set of maximal configurations of a
branching cell $c$ is denoted by $\Omega_{c}$.

It is important to note that while branching cells decomposing a configuration
are disjoint, in general, different branching cells of an es may overlap. This
is because not all of the events that can potentially constitute a branching
cell are enabled at every configuration. Thus, configurations determine their
corresponding branching cells and in this way we say that decomposition
through branching cells is dynamic.

Now the operational definition of pres’s is given by equipping each branching
cell of an es with a probability for its maximal configurations; [1] show
(highly non-trivially) that the operational and abstract definitions give the
same class of structures.

###### Definition 11

A locally finite es $\mathcal{E}$ is _locally randomised_ if each branching
cell $c\in\mathcal{C}$ is equipped with a _local transition probability_
$q_{c}$ on the set $\Omega_{C}$ of configurations that can be chosen within
the cell. The likelihood function $p:\overline{\mathcal{W}}\rightarrow[0,1]$
is defined as:

$\forall v\in\overline{\mathcal{W}},\text{
}p(v)=\prod_{c\in{\Delta}(v)}q_{c}(v\cap c)$

where $\Delta(v)$ denotes the covering of $v$ in $\mathcal{E}$.

$p$ induces a probability measure $\mathbb{P}_{B}$ on the (countable) space
$B$ of stopping prefixes of $\mathcal{E}$; and the full probability measure
$\mathbb{P}$ can be derived from $\mathbb{P}_{B}$ via a construction called
the _distributed product_ and the Prokhorov extension theorem. Hence the
measure $\mathbb{P}$ is called the distributed product of the branching
probabilities $\\{q_{c}:c\in C\\}$.

Further, this definition of likelihood function also applies to the space of
$R$-stopped configurations of $\mathcal{E}$, and so [1] obtains a definition
of probabilistic event structures in which local choice probabilities are
attached either to branching cells or to $R$-stopped configurations.

###  3.3 Categorical notions

It is convenient to have to hand a few items from Winskel’s categorical
toolkit:

###### Definition 12

[24] Let $\mathcal{E}_{0}=(E_{0},Con_{0},\vdash_{0})$ and
$\mathcal{E}_{1}=(E_{1},Con_{1},\vdash_{1})$ be two ses. A _morphism_ from
$\mathcal{E}_{0}$ to $\mathcal{E}_{1}$ is a partial function
$\theta:E_{0}\rightarrow E_{1}$ on events satisfying:

  1. 1.

$X\in Con_{0}\Rightarrow\theta.X\in Con_{1}$

  2. 2.

$\\{e,e^{\prime}\\}\in Con_{0}\;\&\;\theta(e)=\theta(e^{\prime})\Rightarrow
e=e^{\prime}$

  3. 3.

$X\vdash_{0}e\;\&\;\theta(e)\text{ is defined
}\Rightarrow\theta.X\vdash_{1}\theta(e)$

A morphism is _synchronous_ if it is a total function.

As remarked earlier, there is an inclusion $I$ from pes to ses, with an
adjoint functor back. We will need this functor:

###### Definition 13

Given a ses $\mathcal{E}_{0}=(E,Con,\vdash)$, let $\Theta(\mathcal{E}_{0})$ be
the pes $\mathcal{E}_{1}=(P,Con_{P},\leq)$, with isomorphic domain of
configurations, defined as follows.

  1. 1.

$P=\\{\lceil e\rceil_{x}~{}|~{}e\in x\in\mathcal{V}(\mathcal{E})\\}.$

  2. 2.

$p^{\prime}\leq p\Leftrightarrow p^{\prime}\subseteq p.$

  3. 3.

$X\in Con_{P}\Leftrightarrow X\subseteq_{\text{fin}}P~{}\&~{}X\uparrow.$

$\Theta$ maps morphisms thus: if
$\theta\colon\mathcal{E}\to\mathcal{E}^{\prime}$ (induced by an event map
$\theta:E\to E^{\prime}$), then $\Theta(\theta)$ is $\\{\lceil
e\rceil_{x}~{}|~{}e\in
x\in\mathcal{V}(\mathcal{E})\\}\mapsto\\{\lceil\theta(e)\rceil_{x^{\prime}}~{}|~{}\theta(e)\in
x^{\prime}\in\mathcal{V}(\mathcal{E}^{\prime})\\}$.

For a ses $\mathcal{E}_{0}$ we refer to $\Theta(\mathcal{E}_{0})$ as its
associated pes.

The counit of the adjunction is
$\theta\colon\mathcal{E}_{0}\mapsto\theta_{\mathcal{E}_{0}}$, where
$\theta_{\mathcal{E}_{0}}\colon\Theta(\mathcal{E}_{0})\to\mathcal{E}_{0}$ is
the synchronous morphism (of ses) given by
$\theta_{\mathcal{E}_{0}}(p)=e\text{ for }p=\lceil e\rceil_{x}\in P,\;e\in
E\;\&\;x\in\mathcal{V}(\mathcal{E}_{0})$.

##  4 Conflict-driven (Stable or Prime) Event Structures

The difficulty in extending probabilistic notions to rich concurrent
structures such as ses lies in the consistency relation, and ensuring that
causal (in)dependence matches appropriately with probabilistic (in)dependence.
As we have just seen, it is already quite technically intricate for the
relatively simple case of event structures with a binary conflict relation.
Our contribution here is to develop the framework further to allow more
sophisticated consistency relations. In particular, we will define a class of
ses which is sufficient to give a low-level semantics for Petri nets, in which
consistency arises not just out of immediate conflicts, but out of the history
of previous conflicts; and moreover there is the possibility of _confusion_ ,
where the execution of _prima facie_ concurrent events is interfered with by
other events.

In the definition of ses, the consistency predicate $Con$ is required to
satisfy only one condition. Namely, $Y\subseteq X\;\&\;X\in Con\Rightarrow
Y\in Con$. This does not necessarily have to fit with the configurations of
the ses. Consider the following example.

###### Example 1

Let $\mathcal{E}=(E,Con,\vdash)$ be a ses, where
$E=\\{e_{1},e_{2},e_{3},e_{4}\\}$, $\\{e_{1}\\}\vdash e_{2},\\{e_{3}\\}\vdash
e_{4}$, $\\{e_{1},e_{3}\\}\notin Con$ and $\\{e_{2},e_{4}\\}\in Con$. It is
easy to see that even though $e_{2}$ and $e_{4}$ are consistent, they can
never appear together in a configuration. Therefore, the consistency predicate
is not sensible with respect to the configurations. (In terms introduced just
below, the consistency relation here is only recording the immediate
conflicts, not the inherited conflicts.)

We therefore define _sensible_ ses and pes as follows.

###### Definition 14

Let $\mathcal{E}$ be a ses or pes with the consistency relation $Con$. We say
$\mathcal{E}$ is _sensible_ iff $\forall X\in Con\Leftrightarrow\exists
v\in\mathcal{V}(\mathcal{E}).\;X\subseteq v$. If $\mathcal{E}$ is not
sensible, it can be made so by pruning $Con$ of the unreachable consistent
sets.

So far we have described how the consistency predicate in sensible structures
relates to the configurations of that structure. We now define the notions of
conflict and immediate conflict.

###### Definition 15

Two events $e$ and $e^{\prime}$ of a ses are in _conflict_ under a finite
configuration $v$, represented by $e\\#_{v}e^{\prime}$ iff
$\big{(}\\{e\\}\cup\\{e^{\prime}\\}\cup v\big{)}\notin Con$. Then two events
are in conflict, represented by $e\\#e^{\prime}$, iff $\forall
v\in\mathcal{V}.\;e\\#_{v}e^{\prime}$.

Define _immediate conflict_ between two events $e$ and $e^{\prime}$ of a ses
under configuration $v$:

$e\\#_{\mu,v}e^{\prime}\Leftrightarrow_{def}v\vdash e\;\&\;v\vdash
e^{\prime}\;\&\;\\#_{v}\cap(\lceil e\rceil_{v}\times\lceil
e^{\prime}\rceil_{v})=\\{(e,e^{\prime})\\}.$

and define $e\\#_{\mu}e^{\prime}$ iff $\forall
v,v^{\prime}\in\mathcal{V}.\;v\vdash e\;\&\;v^{\prime}\vdash
e^{\prime}\Rightarrow\exists v^{\prime\prime}\subseteq v\cup
v^{\prime}.\;e\\#_{\mu,v^{\prime\prime}}e^{\prime}$.

###### Definition 16

For a set $X\subseteq_{\text{fin}}E$, let ${}_{*}X$ be the set of the sets
consisting of exactly one history $\lceil e\rceil_{v}$ for each event $e$ in
$X$ and configuration $v\ni e$. (That is, for every configuration, ${}_{*}X$
contains a single choice among all the histories that can have produced each
event in $X$.)

We now define a special class of ses, namely, conflict-driven ses. Originally,
their definition arose through considering unfoldings of Petri nets, and so in
[8] they are called ‘net-driven’, but here we abstract away from the net
derivation.

###### Definition 17

A ses $\mathcal{E}=(E,Con,\vdash)$ is called _conflict-driven_ iff it
satisfies the following.

  1. 1.

$\mathcal{E}$ is sensible.

  2. 2.

$\forall X\subseteq_{fin}E.\;X\notin Con\Rightarrow\forall
T\in{}_{*}X.\;\exists e_{1},e_{2}\in\bigcup T.\;e_{1}\\#_{\mu}e_{2}$

  3. 3.

$\forall e,e^{\prime}\in E,v\in\mathcal{V}.\;e\\#_{\mu,v}e^{\prime}\Rightarrow
e\\#e^{\prime}$

Note that from 2 and 3 it follows that $\forall X\subseteq E.\;X\notin
Con\Rightarrow\forall T\in{}_{*}X.\;\exists e_{1},e_{2}\in\bigcup
T.\;e_{1}\\#e_{2}$

As mentioned before, the first characteristic describes that the consistency
predicate is in line with configurations and the second one implies that the
source of inconsistency is a conflict in the past. The last constraint
describes the persistence of conflicts (originally because immediate conflict
in a Petri net is a cause of later conflict).

We can now show that for the associated pes of a conflict-driven ses, the
consistency predicate can be generated from a binary conflict relation:

###### Theorem 1

Let $\mathcal{E}_{0}=(E,Con,\vdash)$ be a conflict-driven ses and let
$\mathcal{E}_{1}=\Theta(\mathcal{E}_{0})=(P,Con_{P},\leq)$ be its associated
pes. Then,we have:

$X\in Con_{P}\Leftrightarrow X\subseteq_{\text{fin}}P\;\&\;\forall
p,p^{\prime}\in X.\neg(p\\#p^{\prime})$

where $p\\#p^{\prime}$ iff $\\{p,p^{\prime}\\}\notin Con_{P}$.

If a pes does have a consistency relation generable from a binary conflict
relation, it can be seen as an es via an inclusion mapping $\hat{I}$. Thus a
conflict-driven ses generates an es.

###### Definition 18

Given a conflict-driven ses $\mathcal{E}$, we denote by $\hat{\mathcal{E}}$ or
$\hat{\Theta}(\mathcal{E})$ the es ${\hat{I}}(\Theta(\mathcal{E}))$, and we
refer to $\hat{\mathcal{E}}$ as the associated es of $\mathcal{E}$. Similarly
we write $\tilde{\theta}_{\mathcal{E}}$ for the adjunct morphism
$\hat{I}(\Theta(\mathcal{E}))\to\Theta(\mathcal{E})\to\mathcal{E}$.

##  5 Probabilistic Jump-free Stable Event Structures

We now consider adjoining probabilities to ses. First we present the
definition of concepts analogous to those of probabilistic event structures.
Then our aim is to derive an isomorphism between the events of branching cells
of conflict-driven ses and their associated es; we find that such isomorphisms
exist if the ses are _jump-free_ , as we shall define.

We assume that the ses in this section are conflict-driven unless stated
otherwise.

###  5.1 Branching Cells on Stable Event Structures

We now define branching cells for ses, in a similar manner and show that in
general, unlike the branching cells of es, they do not form the units of
choice.

###### Definition 19

A subset $P\subseteq E$ is called a prefix of a ses $\mathcal{E}$ iff $\forall
e\in P.\;\exists X\subseteq P.\;X\vdash e$.

Let $\mathcal{E}=(E,Con,\vdash)$ be a ses and let $F$ be a prefix of $E$. Then
$(F,\\{X\cap F:X\in Con\\},\\{(X\cap F,e\in F):X\vdash e\\})$ is a ses (which
is a sub-ses of $\mathcal{E}$). We use $F$ also for the sub-ses induced by
$F$, when no confusion arises. Configurations can then be viewed as consistent
prefixes as before. Concepts of compatibility of configuration and maximal
configurations are defined as for es and we represent the set of maximal
configurations of ses $\mathcal{E}$ by $\Omega(\mathcal{E})$.

In this setting, the _future_ of a configuration $v$ of $\mathcal{E}$ is
$\mathcal{E}^{v}=(E^{v},Con^{v},\vdash^{v})$ where $E^{v}=\\{e\notin
v:\\{e\\}\cup v\in Con\\}$ and $Con^{v},{\vdash^{v}}$ are the natural
restrictions to $E^{v}$. (Note that the future of $v$ includes all events that
might happen, both those directly enabled by $v$ and those completely
independent.)

The notions of $B$-stopped and stopped configurations for ses are similar to
those of es. However, unlike es, given $X$ a subset of events, a canonical
stopping prefix including $X$ cannot be derived. This is because in the
definition of prefix for ses an event can have different sets of events
enabling it. Thus, these notions are defined as follows, recalling the
definition of $\\#_{\mu,v}$ (definition 15).

###### Definition 20

A prefix $B$ of a ses $\mathcal{E}$ is called a stopping prefix if it is
$\\#_{\mu,v}\text{-closed}$ in the following sense:

$\forall v\subseteq B.\;e\in v\;\&\;\exists e^{\prime}\in
E.\;e\\#_{\mu,v}e^{\prime}\Rightarrow e^{\prime}\in B$

A configuration $v$ of $\mathcal{E}$ is called $B$-stopped if $v$ is a maximal
configuration of $B$; $v$ is called stopped if there is a stopping prefix $B$
such that $v$ is $B$-stopped.

Stopping prefixes of a conflict-driven ses have a close relation with the
stopping prefixes of their associated es. To expand this further, we first
observe the relation between $\\#_{\mu,v}$ of a ses and $\\#_{\mu}$ of its
corresponding es by the following immediate lemma:

###### Lemma 1

Given a ses $\mathcal{E}$ and $\hat{\mathcal{E}}=\hat{\Theta}(\mathcal{E})$,
then $e\\#_{\mu,v}e^{\prime}\Leftrightarrow\lceil e\rceil_{v}\\#_{\mu}\lceil
e^{\prime}\rceil_{v}$

Using this lemma we can describe the relation between ses stopping prefixes
and es stopping prefixes as follows.

###### Proposition 1

Given a ses $\mathcal{E}$, then $B$ is a stopping prefix of $\mathcal{E}$ iff
$\hat{\Theta}(B)$ is a stopping prefix of $\hat{\mathcal{E}}$.

###### Proof 1

It is easy to verify that $B$ is a prefix iff $\hat{B}=\hat{\Theta}(B)$ is a
prefix as well (follows from the definition of $\hat{\Theta}$ and
$\tilde{\theta}_{\mathcal{E}}$ (definitions 13, 18) being a morphism). Also,
from lemma 1 it follows that $B$ is $\\#_{\mu,v}$-closed (for $v\subseteq B$)
iff $\hat{B}$ is $\\#_{\mu}$-closed.

The following are the appropriate adaptations of the es definitions:

###### Definition 21

A configuration $v$ of ses $\mathcal{E}$ is R-stopped if there is a non-
decreasing sequence of configurations $(v_{n})$ for $0\leq n<N\leq\infty$ such
that:

  1. 1.

$v_{0}=\varnothing$ and $v=\bigcup_{0{\leq}n<N}v_{n}$ , and

  2. 2.

$\forall n{\geq}0,\text{ }n+1<N\Rightarrow v_{n+1}\ominus v_{n}$ is finite
stopped in $\mathcal{E}^{v_{n}}$.

The sequence is called a valid decomposition of $v$ and if $N<\infty$ then $v$
is said to be finite R-stopped. The set of $R$-stopped configurations of an
ses $\mathcal{E}$ is denoted ${\mathcal{W}(\mathcal{E})}$.

$\mathcal{E}$ is pre-regular, if for every finite configuration $v$ of
$\mathcal{E}$, the set $\\{e\in E\mid v\oplus\\{e\\}\\}$ is finite.

$\mathcal{E}$ is locally finite if for every $e\in E$, there is a finite
stopping prefix of $\mathcal{E}$ containing $e$.

As before, an _initial stopping prefix_ is a minimal non-empty stopping
prefix.

A _branching cell_ of $\mathcal{E}$ and configuration
$v\in\overline{\mathcal{W}}({\mathcal{E}})$ is an initial stopping prefix of
$\mathcal{E}^{v}$. The set of all branching cells of $\mathcal{E}$ is denoted
by $\mathcal{C}(\mathcal{E})$ and the set of maximal configurations of a
branching cell $c$ is denoted by $\Omega_{c}$.

The branching cells which are initial stopping prefixes of $\mathcal{E}^{v}$
are called the branching cells _enabled_ by $v$, and denoted by
$\delta_{\mathcal{E}}(v)$ or $\delta(v)$ if no confusion arises.

###  5.2 Probabilistic Event Structures and Stable Event Structures

We are now ready to add probability to ses. This would be fairly
straightforward, if the branching cells of conflict-driven ses and their
associated es were isomorphic. However, the following example shows why this
is not the case.

###### Example 2

Consider the below ses $\mathcal{E}$, corresponding to the Petri net at the
beginning of the paper, and its associated es $\hat{\mathcal{E}}$, where the
dashed curved lines represent immediate conflicts. The dotted curved line
shows immediate conflict under a particular configuration; in this case
$e_{a}\\#_{\mu,\\{e_{1}\\}}e_{b}$.

$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{a}$$e_{b}$$\tilde{\theta}_{\mathcal{E}}(c_{1})$
A (conflict-driven) stable event structure $\mathcal{E}$
$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{a}$$e_{a}^{\prime}$$e_{b}$$c_{1}$$c_{2}$ The
corresponding es $\hat{\mathcal{E}}=\hat{\Theta}(\mathcal{E})$.

As it can be seen from the figures, $\hat{\mathcal{E}}$ has two branching
cells ($c_{1}$ and $c_{2}$), while $\mathcal{E}$ (which
${}=\theta_{\mathcal{E}}(\hat{\mathcal{E}})$) has only one. To see this, let
us construct the branching cells of $\hat{\mathcal{E}}$. Consider the
configuration $v_{1}=\\{e_{2},e_{4},...\\}$. Having event $e_{2}$ implies that
events $e_{1},e_{3},e_{4},e_{b}$ and $e_{a}$ must be added to the branching
cell because of $\\#_{\mu}$-closure. Thus, $e_{a}^{\prime}$ is not in this
branching cell, but in the next branching cell, consisting of $e_{a}^{\prime}$
only. However, in the ses, both $e_{a}$ and $e_{a}^{\prime}$ of
$\hat{\mathcal{E}}$ are represented by event $e_{a}$ of $\mathcal{E}$.
Therefore, it is not possible to cover $\mathcal{E}$ in any manner that is
consistent with the covering for $\hat{\mathcal{E}}$.

Although in this example $c_{2}$ does not reflect any choice being made, more
complex examples exist where all branching cells have a choice to make.
Therefore, it is not possible to resolve this at the probabilistic level, e.g.
by trying to combine a number of branching cells with respect to their
probabilities.

In order to achieve isomorphic branching cells and avoid the above situation
(and more complex problems), we consider a class of ses (and their associated
es) which forbid these cases, namely, those structures which are _jump-free_.

###### Definition 22

An es is _jump-free_ iff

$\forall e,e^{\prime}.\;e<e^{\prime}\Rightarrow\nexists
e_{1},\ldots,e_{k}.k>1\mathrel{\&}e\\#_{\mu}e_{1},e_{i}\\#_{\mu}e_{i+1}\mathrel{\&}e_{k}\\#_{\mu}e^{\prime}$

for $1\leq i\leq{k}$. A ses is _jump-free_ iff

$\forall e,e^{\prime}.e<_{v}e^{\prime}\Rightarrow\nexists
e_{1},\ldots,e_{k}.k>1\mathrel{\&}e\\#_{\mu,v_{0}}e_{1},e_{i}\\#_{\mu,v_{i}}e_{i+1},e_{k}\\#_{\mu,v_{k}}e^{\prime}$

for $1\leq i\leq{k-1}\mathrel{\&}v_{i}\subseteq v$.

For example, the ses in example 2 is not jump-free as either of the chains of
events $e_{3},e_{4},e_{b}$ and $e_{1},\ldots,e_{b}$ break jump-freeness.

Jump-free es are simpler to deal with, as, unlike es, they are _flat_ in the
following sense.

###### Proposition 2

The branching cells of jump-free es (as initial stopping prefixes) consist of
initial events only (and the converse holds also).

###### Proof 2

Suppose $c$ has non-initial events and let $e\in c$ be such that $\exists
e_{0}\in c.\;e_{0}<e\;\&\;\nexists e_{1}\in c.\;e<e_{1}$. Then there exists an
initial event $e^{\prime}$ s.t. $\nexists e_{0}\in
c.\;e_{0}<e^{\prime}\;\&\;e^{\prime}<e$. Noting that $c$ is an initial
stopping prefix and therefore, $\nexists c^{\prime}.\;c^{\prime}\subset c$,
then in the formation of $\\{e^{\prime}\\}^{*}$, $e$ can only be added to
achieve the closure of $\\#_{\mu}$. Therefore, there must be a chain of events
$e_{1},\ldots,e_{k}$ s.t.
$e^{\prime}\\#_{\mu}e_{1},e_{i}\\#_{\mu}e_{i+1}\;\&\;e_{k}\\#_{\mu}e$. Observe
that $k>1$ as otherwise $\neg(e\\#_{\mu}e_{1})$. Therefore, above chain forms
a jump which is a contradiction and as such $c$ only consists of non-initial
events.

The converse follows immediately from branching cells being closed under
$\\#_{\mu}$.

The same holds for ses:

###### Proposition 3

The branching cells of jump-free ses (as initial stopping prefixes) consist of
initial events only.

###### Proof 3

The proof follows a similar reasoning to that of es, noting that for all the
initial events in $\mathcal{E}^{v}$, $\\#_{\mu}$ is resolved meaning $\forall
v^{\prime}\in\mathcal{V}(\mathcal{E}^{v}).\;e\\#_{\mu,v^{\prime}}e^{\prime}\Rightarrow
e\\#_{\mu}e^{\prime}$.

Recalling that the configurations of a ses and its associated es are
isomorphic, we show in the following theorem that the branching cells of a
jump-free conflict-driven ses and its associated es are isomorphic.

###### Theorem 2

Given a jump-free conflict-driven ses $\mathcal{E}$ and its associated es
$\hat{\mathcal{E}}=\hat{\Theta}(\mathcal{E})$, $\hat{\mathcal{C}}$, the set of
branching cells of $\hat{\mathcal{E}}$, is isomorphic to $\mathcal{C}$, the
set of branching cells of $\mathcal{E}$.

The most important consequence of theorem 2 is that the covering of any
configuration in a ses is exactly the same as that of its corresponding
configuration in its associated es. That is because the configurations in the
future of two isomorphic configurations are also isomorphic and therefore, two
isomorphic configurations have isomorphic coverings. Therefore, all the
probabilistic properties of branching cells of es are applicable to those of
ses, and as such, all the probabilistic machinery described in section 3.2 for
es can be applied to conflict-driven jump-free ses. Thus, for example, the
likelihood function for a ses $\mathcal{E}$,
$p:\overline{\mathcal{W}}\rightarrow\mathbb{R}$ is defined as:

$\forall v\in\overline{\mathcal{W}},\text{
}p(v)=\prod_{c\in{\Delta}(v)}q_{c}(v\cap c)$

##  6 Conclusion

We have introduced a new class of ses called conflict-driven ses, which
includes those ses that arise from Petri nets under the first author’s
‘compact unfoldings’.

We then proceeded to extend the results of [1] to ses, finding that this is
not possible in general, but that it is possible for our new class of ‘jump-
free’ es and ses for which the branching cells consist of events which are not
causally related. We then proved that for such stable event structures and
their associated event structures, the branching cells are isomorphic. Thus,
probabilistic jump-free ses were defined in a similar manner to probabilistic
event structures of [1].

The jump-free notion can be translated back to Petri nets, where it means,
more or less, that confusion is allowed provided that it is not directly
propagated forward by the causality relation. While the jump-free structures
are a larger class than the free-choice structures, they are still far from
complete: both the example nets in our motivation section have jumps. We hope
in future work to find weakenings of the jump-free constraint.

### Acknowledgements

The first author was supported by a studentship from the Laboratory for
Foundations of Computer Science, and by a University of Edinburgh Overseas
Research Scholarship. Both authors were partly supported by EPSRC grant
EP/G012962/1. We are grateful to readers of [8] and earlier versions of this
paper for very helpful comments.

## References

  * [1] Samy Abbes and Albert Benveniste.  True-concurrency probabilistic models branching cells and distributed probabilities for event structures.  Inf. Comput., 204(2):231–274, 2006.
  * [2] Samy Abbes and Albert Benveniste.  True-concurrency probabilistic models: Markov nets and a law of large numbers.  Theoretical Computer Science, 390(2):129–170, 2008.
  * [3] Christel Baier.  On algorithmic verification methods for probabilistic systems.  Universität Mannheim, 1998.
  * [4] Albert Benveniste, Eric Fabre, and Stefan Haar.  Markov nets: probabilistic models for distributed and concurrent systems.  Automatic Control, IEEE Transactions on, 48(11):1936–1950, 2003\.
  * [5] Luca De Alfaro.  Formal verification of probabilistic systems.  PhD thesis, Standford University, 1997.
  * [6] Luca De Alfaro.  Stochastic transition systems.  Springer, 1998.
  * [7] Cyrus Derman.  Finite state Markovian decision processes.  Academic Press, Inc., 1970.
  * [8] Nargess Ghahremani.  Petri Nets, Probability and Event Structures.  PhD thesis, University of Edinburgh, 2014.
  * [9] Stefan Haar.  Probabilistic cluster unfoldings for petri nets.  2002\.
  * [10] Sumit Kumar Jha, Madhavan Mukund, Ratul Saha, and P. S. Thiagarajan.  Distributed markov chains.  In Proc. 16th Int. Conf. on Verification, Model Checking, and Abstract Interpretation (VMCAI), 2015.
  * [11] Claire Jones and Gordon D Plotkin.  A probabilistic powerdomain of evaluations.  In Logic in Computer Science, 1989. LICS’89, Proceedings., Fourth Annual Symposium on, pages 186–195. IEEE, 1989.
  * [12] D. Kartson, G. Balbo, S. Donatelli, G. Franceschinis, and G. Conte.  Modelling with generalized stochastic Petri nets.  John Wiley & Sons, Inc., 1994.
  * [13] Joost-Pieter Katoen.  Quantitative and qualitative extensions of event structures.  PhD thesis, University of Twente, 1996.
  * [14] Amir Pnueli and Lenore D Zuck.  Probabilistic verification.  Information and computation, 103(1):1–29, 1993.
  * [15] Martin L. Puterman.  Markov decision processes: discrete stochastic dynamic programming, volume 414.  Wiley. com, 2009.
  * [16] Michael O. Rabin.  Probabilistic automata.  Information and control, 6(3):230–245, 1963.
  * [17] Roberto Segala.  Modeling and verification of randomized distributed real-time systems.  1996\.
  * [18] Roberto Segala and Nancy Lynch.  Probabilistic simulations for probabilistic processes.  Nordic Journal of Computing, 2(2):250–273, 1995.
  * [19] Regina Tix, Klaus Keimel, and Gordon Plotkin.  Semantic domains for combining probability and non-determinism.  Electronic Notes in Theoretical Computer Science, 222:3–99, 2009\.
  * [20] Daniele Varacca and Mogens Nielsen.  Probabilistic petri nets and mazurkiewicz equivalence.  2003\.
  * [21] Daniele Varacca, Hagen Völzer, and Glynn Winskel.  Probabilistic event structures and domains.  In CONCUR 2004-Concurrency Theory, pages 481–496. Springer, 2004\.
  * [22] Moshe Y. Vardi.  Automatic verification of probabilistic concurrent finite state programs.  In Foundations of Computer Science, 1985., 26th Annual Symposium on, pages 327–338. IEEE, 1985.
  * [23] Hagen Völzer.  Randomized non-sequential processes.  In CONCUR 2001—Concurrency Theory, pages 184–201. Springer, 2001\.
  * [24] Glynn Winskel.  Event structures.  In Advances in Petri Nets, pages 325–392, 1986.
  * [25] Glynn Winskel.  Distributed probabilistic strategies.  In 29th Conference on the Mathematical Foundations of Programming Semantics, 2013.
  * [26] Wang Yi and Kim Guldstrand Larsen.  Testing probabilistic and nondeterministic processes.  In PSTV, volume 12, pages 47–61, 1992.

## Appendix

######  Proof 4 (Proof of Theorem 1)

($\Rightarrow$) follows from the definition of consistency relation. More
precisely, if $\exists p,p^{\prime}\in X.\;p\\#p^{\prime}$ then it follows
that $p$ and $p^{\prime}$ are not consistent (by definition of $\\#$) and
therefore, they are not compatible as configurations of $\mathcal{E}_{0}$.
Thus, $X\notin Con_{P}$ which is a contradiction.

($\Leftarrow$) follows from the definition of conflict-driven ses. More
specifically, suppose by contradiction that there is a finite set of events
$X$ s.t. $\forall p,p^{\prime}\in X.\;\neg(p\\#p^{\prime})$ and $X\notin
Con_{P}$. Let $X=\\{p_{i}\mid p_{i}=\lceil
e_{i}\rceil_{v_{i}}\;\&\;v_{i}\in\mathcal{V}(\mathcal{E}_{0})\\}$. Since
$X\notin Con_{P}$ this implies that $p_{i}$ as configurations of
$\mathcal{E}_{0}$ are not compatible, in other words, if we let
$\bar{X}=\cup\lceil e_{i}\rceil_{v_{i}}$, then $\bar{X}\notin Con$. Now since
$\mathcal{E}_{0}$ is conflict-driven, then for any
$T\in{}_{*}\bar{X}.\;\exists e_{1},e_{2}\in\bigcup T.\;e_{1}\\#e_{2}$. For
such $e_{1},e_{2}$, suppose $p_{1},p_{2}\in X.\;p_{1}=\lceil
e\rceil_{v_{1}}\;\&\;e_{1}\in p_{1}\;\&\;p_{2}=\lceil
e^{\prime}\rceil_{v_{2}}\;\&\;e_{2}\in p_{2}$. Then $p_{1}$ and $p_{2}$ are
not compatible as configurations of $\mathcal{E}_{0}$, therefore
$\\{p_{1},p_{2}\\}\notin Con_{P}$, which contradicts $\forall p,p^{\prime}\in
X.\;\neg(p\\#p^{\prime})$. Therefore, $X$ must be consistent, i.e. $X\in
Con_{P}$.

The proof of theorem 2 requires a few trivial lemmas.

###### Lemma 2

The following facts are immediate from the relevant definitions:

pes are sensible.

Let $\mathcal{E}_{0}$ be a sensible ses and let
$(P,Con_{P},\leq)=\Theta(\mathcal{E})$. Then

$e\leq_{x}e^{\prime}\Leftrightarrow\lceil e\rceil_{x}\subseteq\lceil
e^{\prime}\rceil_{x}$ $X\in Con\Leftrightarrow\forall
v\in\mathcal{V}(\mathcal{E}_{0})\;s.t.\;X\subseteq v.\;\\{\lceil
e\rceil_{v}\mid e\in X\\}\in Con_{P}$

###### Lemma 3

Let $\mathcal{E}$ be a conflict-driven ses with associated es
$\hat{\mathcal{E}}$. Then we have

$e\\#_{\mu,v}e^{\prime}\Leftrightarrow\lceil e\rceil_{v}\\#_{\mu}\lceil
e^{\prime}\rceil_{v}.$

###### Proof 5

Follows trivially from lemma 2 and definitions of $\\#_{\mu,v}$ and
$\\#_{\mu}$.

###### Lemma 4

Let $\mathcal{E}$ be a jump-free conflict-driven ses. Then $\hat{\mathcal{E}}$
is jump-free.

###### Proof 6

Follows trivially from lemmas 2 and 3.

We now establish the desired isomorphism of branching cells. First:

###### Lemma 5

Let $\mathcal{E}$ be a conflict-driven ses. Then, for $p\neq p^{\prime}$ if
$\Theta_{\mathcal{E}}(p)=\Theta_{\mathcal{E}}(p^{\prime})\Rightarrow
p\\#p^{\prime}\;\&\;\neg(p\\#_{\mu}p^{\prime})$, where $\Theta_{\mathcal{E}}$
is the mapping from the events of $\mathcal{E}$ to the events of
$\Theta(\mathcal{E})$ (definition 13).

###### Proof 7

Suppose $\Theta_{\mathcal{E}}(p)=\Theta_{\mathcal{E}}(p^{\prime})=e$, then
$p=\lceil e\rceil_{v}$, $p^{\prime}=\lceil e\rceil_{v^{\prime}}$. Let $v_{0}$
be the subset of $v$ s.t. $v_{0}\vdash_{min}e$ and similarly, let $v_{1}$ be
the subset of $v^{\prime}$ s.t. $v_{1}\vdash_{min}e^{\prime}$. By the
stability axiom it follows that $v_{0}\cup v_{1}\notin Con$. It is then
obvious that $p\\#p^{\prime}$. Since $\mathcal{E}$ is conflict-driven, it
follows that $\exists e_{0}\in v_{0},e_{1}\in v_{1}.\;e_{0}\\#e_{1}$, and
therefore, $\lceil e_{0}\rceil_{v}\\#\lceil e_{1}\rceil_{v^{\prime}}$ and
since $\lceil e_{0}\rceil_{v}<\lceil e\rceil_{v}$ and $\lceil
e_{0}\rceil_{v^{\prime}}<\lceil e\rceil_{v^{\prime}}$ it follows that
$\neg(p\\#_{\mu}p^{\prime})$.

######  Proof 8 (Proof of Theorem 2)

Let $\vartheta=\tilde{\theta}_{\mathcal{E}}$ (definitions 13, 18). First
consider configuration $v$ of $\hat{\mathcal{E}}$ and
$v^{\prime}=\vartheta(v)$ of $\mathcal{E}$. Since configurations of
$\hat{\mathcal{E}}$ and $\mathcal{E}$ are isomorphic, it is clear that
$\exists e\in E\setminus
v.\;v\cup\\{e\\}\in\mathcal{V}(\mathcal{E})\Leftrightarrow\exists
e^{\prime}\in E\setminus
v^{\prime}.\;v^{\prime}\cup\\{e^{\prime}\\}\in\mathcal{V}(\mathcal{E})$. In
other words, every initial event in future of $v$ has an associated initial
event in future of $v^{\prime}$ and vice versa. Let
$\hat{\mathcal{E}}^{v}_{0}$ and $\mathcal{E}^{v^{\prime}}_{0}$ represent the
initial events of each structure, respectively. Then we show that $\vartheta$
yields a bijection between $\hat{\mathcal{E}}^{v}_{0}$ and
$\mathcal{E}^{v^{\prime}}_{0}$.

Suppose $e,e^{\prime}\in\hat{\mathcal{E}}^{v}_{0}$ and
$\vartheta(e)=\vartheta(e^{\prime})=e^{\prime\prime}$. By lemma 5 it follows
that $e\\#e^{\prime}$ and $\neg e\\#_{\mu}e^{\prime}$, i.e. there is a
conflict in their past. But this is a contradiction as they are both initial
events in future of a configuration which is conflict-free. As shown above,
every initial event in future of $v^{\prime}$ has an associated event in
future of $v$, therefore, $\vartheta$ (applied to initial events
$\hat{\mathcal{E}}^{v}$) is onto the initial events of
$\mathcal{E}^{v^{\prime}}$. It then follows that $\vartheta$ yields a
bijection between the events of $\hat{\mathcal{E}}^{v}_{0}$ and
$\mathcal{E}^{v^{\prime}}_{0}$, making them isomorphic.

Furthermore, as we are dealing with the initial events that can occur in
future of $v^{\prime}$ i.e. immediately after $v^{\prime}$, the immediate
conflict relation among the events of $\mathcal{E}^{v^{\prime}}_{0}$ is
resolved, in the sense that it does not depend on any configuration in
$\mathcal{E}_{0}^{v^{\prime}}$, and therefore, is obviously compatible with
the immediate conflict relation of $\hat{\mathcal{E}}^{v}_{0}$. Thus, the
branching cells of $\hat{\mathcal{E}}^{v}_{0}$ and
$\mathcal{E}^{v^{\prime}}_{0}$ are isomorphic, which implies the branching
cells of $\hat{\mathcal{E}}$ and those of $\mathcal{E}$ are isomorphic.