Learning Deterministic One-Counter Automata in Polynomial Time
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912262683361280 |
|---|---|
| author | Mathew, Prince Penelle, Vincent Sreejith, A. V. |
| author_facet | Mathew, Prince Penelle, Vincent Sreejith, A. V. |
| contents | We give an active learning algorithm for deterministic one-counter automata (DOCAs) where the learner can ask the teacher membership and minimal equivalence queries. The algorithm called OL* learns a DOCA in time polynomial in the size of the smallest DOCA, recognising the target language.
All existing algorithms for learning DOCAs, even for the subclasses of deterministic real-time one-counter automata (DROCAs) and visibly one-counter automata (VOCAs), in the worst case, run in exponential time with respect to the size of the DOCA under learning. Furthermore, previous learning algorithms are ``grey-box'' algorithms relying on an additional query type - counter value query - where the teacher returns the counter value reached on reading a given word. In contrast, our algorithm is a ``black-box'' algorithm.
It is known that the minimisation of VOCAs is NP-hard. However, OL* can be used for approximate minimisation of DOCAs. In this case, the output size is at most polynomial in the size of a minimal DOCA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_04525 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Deterministic One-Counter Automata in Polynomial Time Mathew, Prince Penelle, Vincent Sreejith, A. V. Formal Languages and Automata Theory Logic in Computer Science F.3.1; F.4.3 We give an active learning algorithm for deterministic one-counter automata (DOCAs) where the learner can ask the teacher membership and minimal equivalence queries. The algorithm called OL* learns a DOCA in time polynomial in the size of the smallest DOCA, recognising the target language. All existing algorithms for learning DOCAs, even for the subclasses of deterministic real-time one-counter automata (DROCAs) and visibly one-counter automata (VOCAs), in the worst case, run in exponential time with respect to the size of the DOCA under learning. Furthermore, previous learning algorithms are ``grey-box'' algorithms relying on an additional query type - counter value query - where the teacher returns the counter value reached on reading a given word. In contrast, our algorithm is a ``black-box'' algorithm. It is known that the minimisation of VOCAs is NP-hard. However, OL* can be used for approximate minimisation of DOCAs. In this case, the output size is at most polynomial in the size of a minimal DOCA. |
| title | Learning Deterministic One-Counter Automata in Polynomial Time |
| topic | Formal Languages and Automata Theory Logic in Computer Science F.3.1; F.4.3 |
| url | https://arxiv.org/abs/2503.04525 |