Compositional method learns timed models for parts of synchronous systems
Compositional Automata Learning of Timed Synchronous Systems
Formal Languages and Automata Theory
Summary
Building detailed models of systems that have timed parts working together can be hard if you try to learn everything at once. This paper shows a way to learn separate models for each part, even when only watching the whole system. The models can then be combined and behave exactly like the real system. The authors tested their method on many examples, finding it works well and can be faster than older methods.
What this means in practice
- •For embedded systems developers: Automatically obtain separate timing models of components in embedded timed systems for easier analysis and debugging.
- •For industrial control engineers: Build detailed models of control systems composed of synchronous timed parts without internal access to component designs.
Authors
Hanyue Chen, Chang Liu, Miaomiao Zhang
Abstract
Active model learning is a crucial technique for automatically constructing formal models of black-box timed systems. However, existing learning approaches typically construct a single monolithic automaton for a timed system with multiple synchronous components, obscuring its component structure and hindering component-level analysis. We propose a compositional learning approach that constructs a deterministic real-time automaton (RTA) for each component with access only to the target system as a whole. Upon termination, the learned RTAs form a network that exhibits exactly the same timed behaviors as the target system. Within the respective resource limits, our implementation terminates successfully on 213 of the 240 (88.8%) randomly generated benchmark instances and all six adapted case-study benchmarks, and requires less learning time than monolithic approaches on some instances.