Learning Realtime One-Counter Automata
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917774985527296 |
|---|---|
| author | Bruyère, Véronique Pérez, Guillermo A. Staquet, Gaëtan |
| author_facet | Bruyère, Véronique Pérez, Guillermo A. Staquet, Gaëtan |
| contents | We present a new learning algorithm for realtime one-counter automata. Our algorithm uses membership and equivalence queries as in Angluin's L* algorithm, as well as counter value queries and partial equivalence queries. In a partial equivalence query, we ask the teacher whether the language of a given finite-state automaton coincides with a counter-bounded subset of the target language. We evaluate an implementation of our algorithm on a number of random benchmarks and on a use case regarding efficient JSON-stream validation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_09434 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Learning Realtime One-Counter Automata Bruyère, Véronique Pérez, Guillermo A. Staquet, Gaëtan Formal Languages and Automata Theory F.4.3 We present a new learning algorithm for realtime one-counter automata. Our algorithm uses membership and equivalence queries as in Angluin's L* algorithm, as well as counter value queries and partial equivalence queries. In a partial equivalence query, we ask the teacher whether the language of a given finite-state automaton coincides with a counter-bounded subset of the target language. We evaluate an implementation of our algorithm on a number of random benchmarks and on a use case regarding efficient JSON-stream validation. |
| title | Learning Realtime One-Counter Automata |
| topic | Formal Languages and Automata Theory F.4.3 |
| url | https://arxiv.org/abs/2110.09434 |