Active Learning Techniques for Pomset Recognizers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914264160141312 |
|---|---|
| author | Pommellet, Adrien Amrane, Amazigh Delaporte, Edgar Prey, Geoffroy Du Peyron, Oscar |
| author_facet | Pommellet, Adrien Amrane, Amazigh Delaporte, Edgar Prey, Geoffroy Du Peyron, Oscar |
| contents | Pomsets are a promising formalism for concurrent programs based on partially ordered sets. Among this class, series-parallel pomsets admit a convenient linear representation and can be recognized by simple algebraic structures known as pomset recognizers. Active learning consists in inferring a formal model of a recognizable language by asking membership and equivalence queries to a minimally adequate teacher (MAT). We improve existing learning algorithms for pomset recognizers by 1. introducing a new counter-example analysis procedure that is in the best case scenario exponentially more efficient than existing methods 2. adapting the state-of-the-art $L^λ$ algorithm to minimize the impact of exceedingly verbose counter-examples and remove redundant queries 3. designing a suitable finite test suite that ensures general equivalence between two pomset recognizers by extending the well-known W-method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03914 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Active Learning Techniques for Pomset Recognizers Pommellet, Adrien Amrane, Amazigh Delaporte, Edgar Prey, Geoffroy Du Peyron, Oscar Formal Languages and Automata Theory F.4.3 Pomsets are a promising formalism for concurrent programs based on partially ordered sets. Among this class, series-parallel pomsets admit a convenient linear representation and can be recognized by simple algebraic structures known as pomset recognizers. Active learning consists in inferring a formal model of a recognizable language by asking membership and equivalence queries to a minimally adequate teacher (MAT). We improve existing learning algorithms for pomset recognizers by 1. introducing a new counter-example analysis procedure that is in the best case scenario exponentially more efficient than existing methods 2. adapting the state-of-the-art $L^λ$ algorithm to minimize the impact of exceedingly verbose counter-examples and remove redundant queries 3. designing a suitable finite test suite that ensures general equivalence between two pomset recognizers by extending the well-known W-method. |
| title | Active Learning Techniques for Pomset Recognizers |
| topic | Formal Languages and Automata Theory F.4.3 |
| url | https://arxiv.org/abs/2501.03914 |