Learning Event-recording Automata Passively
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912521627107328 |
|---|---|
| author | Majumdar, Anirban Mukherjee, Sayan Raskin, Jean-François |
| author_facet | Majumdar, Anirban Mukherjee, Sayan Raskin, Jean-François |
| contents | This paper presents a state-merging algorithm for learning timed languages definable by Event-Recording Automata (ERA) using positive and negative samples in the form of symbolic timed words. Our algorithm, LEAP (Learning Event-recording Automata Passively), constructs a possibly nondeterministic ERA from such samples based on merging techniques. We prove that determining whether two ERA states can be merged while preserving sample consistency is an NP-complete problem, and address this with a practical SMT-based solution. Our implementation demonstrates the algorithm's effectiveness through examples. We also show that every ERA-definable language can be inferred using our algorithm with a suitable sample. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_03627 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Event-recording Automata Passively Majumdar, Anirban Mukherjee, Sayan Raskin, Jean-François Formal Languages and Automata Theory This paper presents a state-merging algorithm for learning timed languages definable by Event-Recording Automata (ERA) using positive and negative samples in the form of symbolic timed words. Our algorithm, LEAP (Learning Event-recording Automata Passively), constructs a possibly nondeterministic ERA from such samples based on merging techniques. We prove that determining whether two ERA states can be merged while preserving sample consistency is an NP-complete problem, and address this with a practical SMT-based solution. Our implementation demonstrates the algorithm's effectiveness through examples. We also show that every ERA-definable language can be inferred using our algorithm with a suitable sample. |
| title | Learning Event-recording Automata Passively |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2508.03627 |