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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Active Learning Techniques for Pomset Recognizers

  • Adrien Pommellet,
  • Amazigh Amrane,
  • Edgar Delaporte,
  • Geoffroy Du Prey,
  • Oscar Peyron

摘要

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.