Starting with a collection of traces generated by process executions, process
discovery is the task of constructing a simple model that describes the
process, where simplicity is often measured in terms of model size. The
challenge of process discovery is that the process of interest is unknown, and
that while the input traces constitute positive examples of process executions,
no negative examples are available. Many commercial tools discover
Directly-Follows Graphs, in which nodes represent the observable actions of the
process, and directed arcs indicate execution order possibilities over the
actions. We propose a new approach for discovering sound Directly-Follows
Graphs that is grounded in grammatical inference over the input traces. To
promote the discovery of small graphs that also describe the process accurately
we design and evaluate a genetic algorithm that supports the convergence of the
inference parameters to the areas that lead to the discovery of interesting
models. Experiments over real-world datasets confirm that our new approach can
construct smaller models that represent the input traces and their frequencies
more accurately than the state-of-the-art technique. Reasoning over the
frequencies of encoded traces also becomes possible, due to the stochastic
semantics of the action graphs we propose, which, for the first time, are
interpreted as models that describe the stochastic languages of action traces.

基于进程追踪的过程发现中，我们提出了一种基于语法推理的新方法来发现准确描述输入追踪的小图模型，通过设计和评估一种遗传算法，支持推理参数收敛至发现有趣模型的区域。实验证实我们的新方法可以构建更小的模型，准确地表示输入追踪及其频率，并首次将行动图解释为描述行动迹线的随机语言模型。