FoldA: Computing Partial-Order Alignments Using Directed Net Unfoldings

• URL: http://arxiv.org/abs/2506.08627v1
• Date: Tue, 10 Jun 2025 09:44:05 GMT
• Title: FoldA: Computing Partial-Order Alignments Using Directed Net Unfoldings
• Authors: Douwe Geurtjens, Xixi Lu,
• Abstract summary: This paper proposes a new technique for computing partial-order alignments on the fly using directed Petri net unfoldings, named FoldA.<n>We evaluate our technique on 485 synthetic model-log pairs and compare it against Astar- and Dijkstra-alignments on 13 real-life model-log pairs and 6 benchmark pairs.
• Score: 0.6906005491572401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conformance checking is a fundamental task of process mining, which quantifies the extent to which the observed process executions match a normative process model. The state-of-the-art approaches compute alignments by exploring the state space formed by the synchronous product of the process model and the trace. This often leads to state space explosion, particularly when the model exhibits a high degree of choice and concurrency. Moreover, as alignments inherently impose a sequential structure, they fail to fully represent the concurrent behavior present in many real-world processes. To address these limitations, this paper proposes a new technique for computing partial-order alignments {on the fly using directed Petri net unfoldings, named FoldA. We evaluate our technique on 485 synthetic model-log pairs and compare it against Astar- and Dijkstra-alignments on 13 real-life model-log pairs and 6 benchmark pairs. The results show that our unfolding alignment, although it requires more computation time, generally reduces the number of queued states and provides a more accurate representation of concurrency.

Related papers

• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• COrAL: Order-Agnostic Language Modeling for Efficient Iterative Refinement [80.18490952057125]
  Iterative refinement has emerged as an effective paradigm for enhancing the capabilities of large language models (LLMs) on complex tasks. We propose Context-Wise Order-Agnostic Language Modeling (COrAL) to overcome these challenges. Our approach models multiple token dependencies within manageable context windows, enabling the model to perform iterative refinement internally.
  arXiv  Detail & Related papers  (2024-10-12T23:56:19Z)
• Efficient Online Computation of Business Process State From Trace Prefixes via N-Gram Indexing [0.5141137421503899]
  Given a process model and an event log containing trace prefixes of ongoing cases of a process, map each case to its corresponding state in the model.<n>An approach to this state computation problem is to perform a token-based replay of each trace prefix against the model.<n>This paper proposes a method that, given a trace prefix of an ongoing case, computes its state in constant time using an index that represents states as n-grams.
  arXiv  Detail & Related papers  (2024-09-09T14:28:24Z)
• Bisimulation Learning [55.859538562698496]
  We compute finite bisimulations of state transition systems with large, possibly infinite state space. Our technique yields faster verification results than alternative state-of-the-art tools in practice.
  arXiv  Detail & Related papers  (2024-05-24T17:11:27Z)
• Non-autoregressive Sequence-to-Sequence Vision-Language Models [59.445765313094434]
  We propose a parallel decoding sequence-to-sequence vision-language model that marginalizes over multiple inference paths in the decoder.<n>The model achieves performance on-par with its state-of-the-art autoregressive counterpart, but is faster at inference time.
  arXiv  Detail & Related papers  (2024-03-04T17:34:59Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Online Time Series Anomaly Detection with State Space Gaussian Processes [12.483273106706623]
  R-ssGPFA is an unsupervised online anomaly detection model for uni- and multivariate time series. For high-dimensional time series, we propose an extension of Gaussian process factor analysis to identify the common latent processes of the time series. Our model's robustness is improved by using a simple to skip Kalman updates when encountering anomalous observations.
  arXiv  Detail & Related papers  (2022-01-18T06:43:32Z)
• CoCoMoT: Conformance Checking of Multi-Perspective Processes via SMT (Extended Version) [62.96267257163426]
  We introduce the CoCoMoT (Computing Conformance Modulo Theories) framework. First, we show how SAT-based encodings studied in the pure control-flow setting can be lifted to our data-aware case. Second, we introduce a novel preprocessing technique based on a notion of property-preserving clustering.
  arXiv  Detail & Related papers  (2021-03-18T20:22:50Z)
• Conformance Checking of Mixed-paradigm Process Models [1.8122712065585906]
  Mixed-paradigm process models integrate strengths of procedural and declarative representations like Petri nets and Declare. A key research challenge for the proliferation of mixed-paradigm models for process mining is the lack of corresponding conformance checking techniques. We devise the first approach that works with intertwined state spaces of mixed-paradigm models.
  arXiv  Detail & Related papers  (2020-11-23T17:04:33Z)
• Efficient Conformance Checking using Approximate Alignment Computation with Tandem Repeats [0.03222802562733786]
  Conformance checking aims to find and describe the differences between a process model capturing the expected process behavior and a corresponding event log recording the observed behavior. Alignments are an established technique to compute the distance between a trace in the event log and the closest execution trace of a corresponding process model. We propose a novel approximate technique that uses pre- and post-processing steps to compress the length of a trace and recompute the alignment cost.
  arXiv  Detail & Related papers  (2020-04-02T03:50:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.