Active Learning Techniques for Pomset Recognizers
摘要
Series-parallel pomsets are a promising mathematical formalism for concurrent programs, as they can be recognized by simple algebraic structures known as pomset recognizers. Active learning consists in inferring a formal model of a system by interactively probing its behavior through queries to a Minimally Adequate Teacher (MAT). We improve existing learning algorithms for pomset recognizers by 1. designing a new counterexample analysis procedure that is in the best case scenario exponentially more efficient than existing techniques, 2. introducing and implementing a new algorithm \( PL ^\lambda \) that extends the state-of-the-art \(L^\lambda \) algorithm to pomset recognizers, minimizing the impact of exceedingly verbose counterexamples and removing redundant queries, and 3. designing a suitable finite test suite that ensures equivalence between two pomset recognizers by adapting the well-known W-method.