💻 computer science

Extended Compositional Learning Algorithm for Synchronous Parallel Automata

This paper presents an extended compositional learning algorithm for synchronous parallel automata that relaxes the restrictive global uniqueness assumption on synchronizing actions, thereby enabling the scalable and correct extraction of component models from realistic black-box systems with significantly fewer resources than monolithic approaches.

Original authors: Mahboubeh Samadi, Aryan Bastany, Hossein Hojjat

Published 2026-09-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mahboubeh Samadi, Aryan Bastany, Hossein Hojjat

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine trying to understand a complex machine, like a car engine or a bank security system, but you cannot open the hood or read the manual. You can only press buttons and watch what happens. This is the challenge of reverse-engineering "black-box" systems. Scientists have developed a method called active learning to solve this. In this process, a computer program acts as a curious student, asking questions to a "teacher" who knows the system inside out. By sending in sequences of commands and recording the responses, the student builds a map of how the machine works, eventually creating a precise model of its behavior. This is incredibly useful for checking if software is safe or for understanding old systems where the original designers are long gone.

However, there is a catch. When the machine is very large and made of many interacting parts, the student gets overwhelmed. The number of questions needed to map the whole thing grows so fast that it becomes impossible to finish the job. To fix this, researchers previously tried a smarter approach: instead of learning the whole machine at once, they tried to learn each small part separately and then snap the pieces together. But this earlier method had a strict rule that made it fail in many real-world situations. It assumed that whenever two parts of the machine talked to each other, they had to say the exact same thing every single time. In the messy reality of modern software, parts often communicate using the same signal but produce different results depending on the situation. The old method couldn't handle this, leaving many complex systems beyond its reach.

In this new study, researchers from universities in Iran have fixed that limitation. They created an upgraded version of the learning algorithm that allows parts of a system to communicate using the same signal while producing different outputs, as long as those outputs match up correctly at the exact moment the parts connect. Think of it like two people speaking the same language but with different accents; they can still understand each other perfectly when they meet, even if their voices sound different elsewhere. The researchers proved mathematically that their new method, which they call ESCL*, always finishes its work and correctly identifies the individual parts of the system. They showed that by relaxing the old, overly strict rule, they could learn complex systems that the previous method would have rejected or gotten wrong.

To test their idea, the team ran their algorithm on two types of challenges. First, they used realistic examples from the real world, including a software system used in Volkswagen cars to control comfort features and a security protocol used by bank cards. These are complex, high-stakes systems where mistakes are not an option. Second, they generated thousands of synthetic systems that mimicked the way computers connect in real networks, such as rings or stars of devices. In every case, they compared their new method against the standard way of learning, which tries to map the entire system as one giant block. The results were clear: as the systems got bigger and more complicated, the standard method struggled, requiring an explosion of questions and time. The new method, however, scaled much better. It learned the same systems using significantly fewer questions and resets, proving that breaking a problem down into smaller, interacting pieces is the key to understanding the largest machines.

The researchers also looked closely at the cost of this improvement. Because their new method is more flexible, it has to do a bit more checking to make sure the parts are connecting correctly. This means it asks slightly more questions than the older, stricter version of the same technique. However, this extra cost is a small price to pay for the ability to learn systems that were previously impossible to model. The study confirms that by allowing for more realistic communication between parts, scientists can now build accurate models of complex, parallel systems without getting lost in the details. This advancement opens the door to analyzing a wider range of critical software, from automotive safety systems to financial security protocols, ensuring they behave exactly as they should.

Technical Summary: Extended Compositional Learning Algorithm for Synchronous Parallel Automata

Problem Statement
Active automata learning is a powerful technique for extracting formal behavioral models from black-box systems, yet applying it monolithically to large-scale industrial systems often faces scalability challenges due to the quadratic scaling of queries with the number of states. Compositional learning offers a solution by learning systems through their individual components. However, previous compositional approaches for synchronous parallel systems, specifically the authors' prior work (SCL*), relied on a restrictive assumption: every synchronizing action must produce a globally unique output across the entire system. In realistic black-box systems, this assumption is often too strong, as synchronizing actions may produce different outputs globally while remaining consistent only at the specific points where components synchronize. This restriction prevents the learning of many realistic systems where global output uniqueness does not hold, potentially leading to output non-determinism in the composed model.

Methodology: The ESCL Algorithm*
To address these limitations, the authors propose ESCL* (Extended Synchronous Compositional Learning), an extension of the SCL* algorithm. The core innovation is the relaxation of the global output uniqueness constraint. ESCL* operates under the condition that synchronizing actions need only produce identical outputs at the specific synchronization points where components interact, rather than globally across all system states.

The algorithm functions as follows:

Initial Partitioning: It begins with an initial cover of the system's input alphabet, partitioning actions into singleton sets, assuming all actions are potentially synchronizing.
Iterative Learning and Verification: The algorithm learns individual components using the standard $L^*$ algorithm on projected alphabets. It then constructs the synchronous parallel composition of these learned components.
Counter-Example Processing: When the teacher (the system under learning) provides a counter-example, the algorithm analyzes the sequence to determine if actions belong to the same component.
Refinement of Synchronization: Unlike SCL*, which removes an action from the synchronizing set if it produces different outputs anywhere, ESCL* verifies output consistency specifically at synchronization points. If a shared action produces conflicting outputs at a synchronization point, the algorithm concludes the action is not a true synchronizing action and merges the input sets containing that action.
Termination: This process iterates, refining the partition of input alphabets and the set of synchronizing actions until the composed model is equivalent to the system under learning.

The paper provides formal proofs for the termination of the algorithm and the correctness of the learned component models, demonstrating that the final input cover correctly identifies dependent actions and valid synchronizing actions.

Key Contributions
The paper makes three primary contributions:

Algorithmic Extension (ESCL):* The introduction of ESCL*, which relaxes the global output uniqueness assumption for synchronizing actions. This allows the algorithm to handle systems where synchronizing actions have different outputs globally but remain consistent at communication points, thereby preventing output non-determinism in the composed model.
Theoretical Guarantees: A formal proof establishing that ESCL* terminates and correctly learns the individual component models and their synchronization structure without prior knowledge of the system's topology or alphabets.
Empirical Evaluation: A comprehensive evaluation using both synthetic benchmarks (inspired by real-world network topologies like point-to-point, star, mesh, and ring) and realistic case studies (an industrial automotive Body Comfort System and a bank card security protocol).

Results
The experimental results demonstrate that ESCL* significantly outperforms monolithic $L^*$ learning in terms of scalability.

Scalability: As the number of states and components increases, ESCL* requires significantly fewer input symbols and resets compared to monolithic $L^*$ . The performance gap widens with system complexity, whereas monolithic learning suffers from exponential state-space growth.
Trade-offs: The paper notes that while ESCL* is more applicable to a broader class of systems than its predecessor SCL*, it incurs a higher query cost (more resets and input symbols) than SCL*. This is because ESCL* must verify output consistency at each synchronization point individually, whereas SCL* relied on a simpler global output check.

Significance
The authors position the significance of this work as bridging the gap between theoretical compositional learning and realistic black-box system analysis. By removing the overly restrictive assumption of global output uniqueness, ESCL* enables the automated learning of complex synchronous parallel systems that were previously intractable or required incorrect decomposition under SCL*. The algorithm successfully discovers the number of components, their individual alphabets, and their synchronization patterns on-the-fly. The authors conclude that while there is a trade-off in query efficiency compared to the more restrictive SCL*, the gain in applicability to realistic systems justifies the approach, offering a scalable alternative to monolithic learning for complex industrial and security protocols.

Technical Summary: Extended Compositional Learning Algorithm for Synchronous Parallel Automata

More like this