Computation of the Transient in Max-Plus Linear Systems via SMT-Solving

Alessandro Abate, Alessandro Cimatti, Andrea Micheli, Muhammad Syifa'ul Mufid

Abstract

Max-Plus Linear (MPL) systems are a specialized class of discrete-event systems used to model processes where synchronization is paramount, such as manufacturing lines and railway networks. A fundamental property of these systems is their eventual convergence to a periodic steady state. The number of steps required to reach this state is known as the transient. This paper introduces a novel methodology for computing the transient by framing the problem as a Satisfiability Modulo Theories (SMT) query. By transitioning from iterative matrix multiplication to Difference Logic (RDL) encoding, the authors provide a scalable solution that enables both efficient computation for large-scale systems and the synthesis of initial states leading to desired periodic behaviors.

Introduction

Max-Plus Linear (MPL) systems are characterized by operations in the $(\mathbb{R} \cup \{-\infty\}, \max, +)$ semiring. They are particularly effective at modeling systems where events must wait for multiple predecessors to complete (synchronization) but do not compete for resources (no concurrency). Examples include biological pathways, digital circuits, and transportation networks.

Figure 1: A graphical representation of a Max-Plus Linear system, illustrating the synchronization and feedback loops typical of discrete-event processes.

A critical parameter in the analysis of MPL systems is the transient length. In applications like reachability analysis or bounded model checking, the transient serves as a "completeness threshold"—the point beyond which the system's behavior becomes predictable and periodic, obviating the need for further simulation.

The Challenge of Transient Computation

Traditionally, the transient is found through iterative matrix multiplication: $x(k+1) = A \otimes x(k)$. One continues this process until a periodic pattern emerges. However, for high-dimensional systems or those with inherently long transients, this iterative approach is computationally prohibitive. Furthermore, traditional methods struggle to identify how specific initial states influence the transient length.

Methodology

The authors shift the paradigm from linear algebra to formal logic.

  1. Logical Encoding: Max-plus expressions, involving max and +, are translated into Difference Logic (RDL). This allows the system's evolution to be represented as a set of constraints of the form $x_i - x_j \le c$.
  2. SMT-Based Refinement: Instead of a linear step-by-step simulation, the proposed algorithm (Algorithms 2 & 3) uses an SMT solver to search for counterexamples. If the solver finds an initial state that has not yet reached periodicity within a guessed transient length, it uses this state to "jump" to a more accurate estimate.
  3. Spatial Synthesis: The logical framework allows for the synthesis of the entire set of initial states that result in a specific transient or periodic behavior, effectively partitioning the state space.

Experimental Evaluation

The approach was benchmarked using 1,000 randomly generated irreducible matrices with dimensions ($n$) ranging from 4 to 40 and varying densities. The SMT-based method (utilizing the Yices 2.2 solver) was compared against standard iterative benchmarks.

Key Results and Insights

  • The "Jump" Advantage: SMT solvers do not need to simulate every step. By asking "Is there any state that isn't periodic yet?", the solver can find problematic states that traditional iterative methods would only encounter much later.
  • The Cross-Over Point: For systems with small transients, the overhead of the SMT solver makes traditional methods faster. However, as the transient length ($k_0$) and cyclicity ($c$) increase, the SMT approach becomes dominant. For a dimension of $n=40$, the SMT method typically outperforms traditional methods when $k_0 + c > 150$.
  • Scalability and Robustness: The SMT approach is particularly effective for "small-but-deep" systems—those with low dimensions but very long transients. In these cases, it can finish in seconds where iterative methods might take minutes or fail to terminate.

Limitations and Future Work

While the algorithm is guaranteed to terminate for "boundedly periodic" systems, it may require a maximum bound for "unboundedly periodic" cases. Additionally, increasing the number of finite elements in the matrix increases the complexity of the SMT formulas. Future work aims to extend this framework to more general model checking, allowing for the verification of complex temporal logic properties within max-plus dynamics.

Summary updated

Abstract

This paper proposes a new approach, grounded in Satisfiability Modulo Theories (SMT), to study the transient of a Max-Plus Linear (MPL) system, that is the number of steps leading to its periodic regime. Differently from state-of-the-art techniques, our approach allows the analysis of periodic behaviors for subsets of initial states, as well as the characterization of sets of initial states exhibiting the same specific periodic behavior and transient. Our experiments show that the proposed technique dramatically outperforms state-of-the-art methods based on max-plus algebra computations for systems of large dimensions.
BibTeX
@inproceedings{abate2020computation,
  author = {Alessandro Abate and Alessandro Cimatti and Andrea Micheli and Muhammad Syifa'ul Mufid},
  title = {{Computation of the Transient in Max-Plus Linear Systems via SMT-Solving}},
  booktitle = {FORMATS},
  year = {2020},
  doi = {10.1007/978-3-030-57628-8\_10},
}
Figure