Concurrent Context-Free Grammar for Parsing Business Processes with Iterated Shuffles

Trace parsing, a technique for obtaining the correspondence between a trace, which is a string of activities, and a process model, forms the basis of process mining. Conventional trace parsing methods have not considered process models with concurrent loops (CLOOPs), in which a certain sub-process is executed in indefinite numbers of concurrent executions, despite their importance. In this paper, we propose a new formal grammar, a Concurrent Context-Free Grammar (CCFG), which can handle CLOOPs. CCFGs are a generalization of context-free grammars, which can handle concurrent strings allowing parallelism among strings. This simple generalization adds a new operator corresponding to a CLOOP to process trees, a type of process model, and greatly extends the representational capability of process trees. This paper also introduces a trace parsing method for a CCFG. This allows the CCFG to verify whether a trace can be derived from the process model, and the CCFG can be used for conformance checking.