Skip to content

Tuesday, 28 February 2017: NODES Seminar, Newcastle

General meeting of all members of NODES and their PhD students.


Room TR4, 4th Floor, Herschel Building, Newcastle University


14.00-14.45 Andrew Wade (Durham, Maths): Convex hulls of random walks
-15.30 Tea/Coffee break
-16.15 Victor Khomenko (Newcastle, CS): Canonical Prefixes of Petri Net Unfoldings

Andrew Wade (Durham, Maths): Convex hulls of random walks

Abstract:  On each of n unsteady steps, a drunken gardener drops a seed. Once the flowers have bloomed, what is the minimum length of fencing required to enclose the garden? What is its area? I will describe recent work on the convex hull of planar random walk, concerned in particular with the large-n asymptotics of its perimeter length and area. We provide variance asymptotics and distributional limit theorems. Of the four combinations of the two quantities (perimeter and area) in the two regimes (zero drift or non-zero drift for the steps of the walk), one limit is Gaussian; three are not.

This talk is mostly based on joint work with Chang Xu (Strathclyde); I’ll also mention ongoing work with Ostap Hryniv and James McRedmond (Durham).

Victor Khomenko (Newcastle, CS): Canonical Prefixes of Petri Net Unfoldings

Petri net unfolding prefixes are used for efficient formal verification of concurrent systems. For this, they have to be finite and complete, i.e. preserve the sufficient information about the original system to be able to decide whether a particular property holds. A key aspect is how to truncate the full (usually infinite) unfolding in such a way that the resulting prefix is guaranteed to be finite and complete. We present a new theoretical framework that allows one to define the unique canonical prefix of the unfolding. Canonical prefixes are complete in the new, stronger sense, and we provide necessary and sufficient conditions for its finiteness, as well as upper bounds on its size in certain cases. A surprising result is that the existing unfolding algorithms, despite being non-deterministic, always generate this canonical prefix.


Snapshots of the talks