Quantitative Deadlock Analysis in Petri Nets using Inconsistency Measures

Petri Nets are often used to describe, execute, analyze and improve business processes. A special area of interest is the detection of possible deadlocks. Deadlocks can harm the proper execution of business processes which may lead to errors or even impossible business process execution, and, in turn, economic loss. In most cases, it is only determined whether a deadlock can occur, in order to eliminate or avoid it. For this, it is necessary to manipulate the behavior of the net, and thus change it. A so far little considered question is how the severity of the potential to encounter a deadlock can be formally investigated and assessed, without altering the net. This could be useful, for example, to assess and compare systems and processes. In a naive approach, the exhaustive calculation of all possible states of the net would be necessary to check in how many of them a deadlock occurs. This is not reasonable in most cases due to the often high to potentially indefinite number of reachable states. In this paper, approaches are developed to approximate the termination potential of an ordinary marked Petri Net through structural analysis. We do this by leveraging approaches from inconsistency measurement, which is a field within Artificial Intelligence to quantitatively assess the severity of inconsistency in formal knowledge representation formalisms. We develop six different measures for the Petri Net setting and investigate their formal properties, in particular wrt. some rationality postulates that were also adapted from the field of inconsistency measurement.