Counting Finite Transition Sequences of Block Structured Workflow Nets

摘要

This paper presents a method to quantify structurally, the exact number of finite traces in block structured workflow nets (BSWFN). First, the BSWFN are recursively defined, where two types of subnets, named AND blocks and OR blocks, may contain nested blocks. Then, an efficient approach that avoids the reachability analysis is proposed; it allows assessing the finite behaviour of BSWFN from its structure. The technique includes counting techniques for basic blocks and composition of blocks; a global counting algorithm is outlined as well as examples treated with its software implementation.