Automata learning algorithms are essential for constructing models of black-box systems, enabling their verification and analysis. Generally, these models represent a type of automata that follows a Myhill-Nerode-like theorem where constructing a model involves approximating Myhill-Nerode classes. One of the earliest such algorithms is Dana Angluin's L*. It constructs a minimal deterministic automaton for a given system whose behavior can be described by a regular language, using membership and equivalence queries. Many optimizations and extensions of this algorithm have been developed to improve efficiency and to learn automata with varying levels of expressiveness.

 

An extension of L* for recognizable languages of series-parallel pomsets was introduced by Tobias Kappé et al, along with a transformation from the underlying algebras to pomset automata. Their learning algorithm infers a pomset recognizer: a bimonoid M equipped with a function mapping letters to M and a subset of M witnessing acceptation. We enhance the L* algorithm for learning pomset recognizers by adapting various techniques initially applied in algorithms for learning regular languages over words. Specifically, we extend the Rivest and Shapire counterexample decomposition theorem to the case of series-parallel pomsets. Furthermore, to remedy the issue of submitting equivalence queries to a black box model, we design a suitable finite test suite that ensures general equivalence between two pomset recognizers by extending the well-known W-method.