Demodocos is a test and flip net synthesis tool implementing a linear algebraic polynomial time algorithm. Computations are done in the Z/2Z ring. Test and flip nets extend elementary net systems by allowing test to zero, test to one and flip arcs. The effect of flip arcs is to complement the marking of the place. While the net synthesis problem has been proved to be NP hard for elementary net systems, thanks to flip arcs, the synthesis of test and flip nets can be done in polynomial time. Test and flip nets have the required expressivity to give concise and accurate representations of processes such as those found in maintenance operation of complex mechanical systems (for instance, maintenance processes of marine or industrial Diesel engines) or, most importantly, surgical processes (models of types of surgical operations). Test and flip nets can express causality and conflict relations. The tool takes as input either standard XES log files (a standard XML file format for process mining tools) or a specific XML file format for surgical applications. The output is a test and flip net, solution of the following synthesis problem: Given a finite input language (log file), compute a net, which language is the least language in the class of test & flip net languages, containing the input language.
This work has received a French government support granted to the CominLabs excellence laboratory and managed by the National Research Agency in the “Investing for the Future” program under reference ANR-10-LABX-07-01.
Benoît Caillaud, Aurélien Lamercerie (PhD student)