Foundations of Reactive Synthesis for Declarative Process Specifications

Luca Geatti, Marco Montali, Andrey RivkinAAAI 2024 · DOI

Abstract

This research establishes the theoretical and algorithmic foundations for automatically generating "correct-by-construction" controllers for business processes defined using the DECLARE language. By leveraging a technique known as "pastification," the authors reduce the computational complexity of reactive synthesis from 2EXPTIME to a more manageable EXPTIME, introducing a symbolic algorithm designed for practical implementation in complex process environments.

Introduction: The Challenge of Reactive Synthesis

In Business Process Management (BPM), declarative languages like DECLARE are used to describe what should happen (e.g., "if an order is paid, it must eventually be shipped") rather than prescribing a rigid flowchart. This flexibility is powerful but introduces complexity when processes involve a Controller (the system) interacting with an unpredictable Environment (customers or external partners).

A sample DECLARE process model illustrating various constraints between activities.

The core challenge is Reactive Synthesis: automatically generating a strategy for the Controller that guarantees all rules are followed regardless of the Environment's actions. Standard approaches using Linear Temporal Logic over finite traces (LTLf) are computationally expensive, typically requiring doubly exponential time (2EXPTIME) relative to the specification size.

Methodology: Pastification and Symbolic DFAs

The authors propose a three-step approach to make synthesis feasible for DECLARE specifications:

  1. Assume-Guarantee Synthesis: The problem is formalized as a game where the Controller must satisfy its requirements under the assumption that the Environment also adheres to specific rules.
  2. Pastification: This is the central innovation. While standard temporal logic is forward-looking ("eventually $X$ will happen"), the authors demonstrate that every DECLARE pattern can be translated into a "pure-past" formula ("if $Y$ is happening now, it is because $X$ happened previously").
  3. Symbolic DFA Construction: Instead of building explicit state machines that suffer from state explosion, the authors utilize Symbolic Deterministic Finite Automata (DFAs). These represent states and transitions using Boolean formulas, allowing the handling of larger state spaces by exploiting logical symmetries.

Key Insights: Linear Growth and Efficiency

A significant discovery in this work is that while general LTLf formulas can grow exponentially when converted to the past, DECLARE patterns only grow linearly. This specific property is what allows the complexity to drop from 2EXPTIME to EXPTIME.

Table mapping standard DECLARE templates to their LTLf formalizations and efficient pastified equivalents.

Pure-past formulas are inherently easier to convert into automata because they do not require "guessing" the future (nondeterminism). A deterministic machine can be built directly from the past requirements. Furthermore, the paper distinguishes between general logic and the "simple traces" common in BPM, where actions occur sequentially and players alternate turns.

Results and Complexity Breakthrough

The authors prove that reactive synthesis for DECLARE is EXPTIME-complete, a major theoretical improvement over general LTLf synthesis. They provide a novel encoding of pure-past LTLf into symbolic DFAs that is more succinct than previous methods, avoiding "counter bits" and reducing the number of necessary state variables. This work includes a complete formal catalog mapping standard DECLARE templates to their new, efficient "pastified" equivalents.

Limitations and Future Directions

While the theoretical framework is robust, empirical performance benchmarks against existing LTLf synthesis tools (such as Strix or Lydia) remain for future work. Additionally, the authors plan to investigate strategy optimization—moving beyond finding any valid strategy to finding the most efficient one for business operations. These automata-based techniques also hold promise for improving runtime monitoring and automated process discovery from event logs.

Summary updated

BibTeX
@inproceedings{geatti2024foundations,
  author = {Luca Geatti and Marco Montali and Andrey Rivkin},
  title = {{Foundations of Reactive Synthesis for Declarative Process Specifications}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i16.29690},
}
Figure