Learning Automata with Name Allocation
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_ | 1866915891922337792 |
|---|---|
| author | Frank, Florian Milius, Stefan Rot, Jurriaan Urbat, Henning |
| author_facet | Frank, Florian Milius, Stefan Rot, Jurriaan Urbat, Henning |
| contents | Automata over infinite alphabets have emerged as a convenient computational model for processing structures involving data, such as nonces in cryptographic protocols or data values in XML documents. We introduce active learning methods for bar automata, a species of automata that process finite data words represented as bar strings, which are words with explicit name binding letters. Bar automata have pleasant algorithmic properties. We develop a framework in which every learning algorithm for standard deterministic or nondeterministic finite automata over finite alphabets can be used to learn bar automata, with a query complexity determined by that of the chosen learner. The technical key to our approach is the algorithmic handling of $α$-equivalence of bar strings, which allows bridging the gap between finite and infinite alphabets. The principles underlying our framework are generic and also apply to bar Büchi automata and bar tree automata, leading to the first active learning methods for data languages of infinite words and finite trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11947 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Automata with Name Allocation Frank, Florian Milius, Stefan Rot, Jurriaan Urbat, Henning Formal Languages and Automata Theory 68Q45 F.4.3 Automata over infinite alphabets have emerged as a convenient computational model for processing structures involving data, such as nonces in cryptographic protocols or data values in XML documents. We introduce active learning methods for bar automata, a species of automata that process finite data words represented as bar strings, which are words with explicit name binding letters. Bar automata have pleasant algorithmic properties. We develop a framework in which every learning algorithm for standard deterministic or nondeterministic finite automata over finite alphabets can be used to learn bar automata, with a query complexity determined by that of the chosen learner. The technical key to our approach is the algorithmic handling of $α$-equivalence of bar strings, which allows bridging the gap between finite and infinite alphabets. The principles underlying our framework are generic and also apply to bar Büchi automata and bar tree automata, leading to the first active learning methods for data languages of infinite words and finite trees. |
| title | Learning Automata with Name Allocation |
| topic | Formal Languages and Automata Theory 68Q45 F.4.3 |
| url | https://arxiv.org/abs/2502.11947 |