Feasability of Learning Weighted Automata on a Semiring
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912533430927360 |
|---|---|
| author | Daviaud, Laure Johnson, Marianne |
| author_facet | Daviaud, Laure Johnson, Marianne |
| contents | Since the seminal work by Angluin and the introduction of the L*-algorithm, active learning of automata by membership and equivalence queries has been extensively studied to learn various extensions of automata. For weighted automata, algorithms for restricted cases have been developed in the literature, but so far there was no global approach or understanding how these algorithms could apply (or not) in the general case. In this paper we chart the boundaries of the Angluin approach. We use a class of hypothesis automata which are constructed, in Angluin's style, by using membership and equivalence queries and solving certain finite systems of linear equations over the semiring, and we show the theoretical limitations of this approach. We classify functions with respect to how guessable they are, corresponding to the existence of hypothesis automata computing a given function, and how such an hypothesis automaton can be found. Of course, from an algorithmic standpoint, knowing that a solution (hypothesis automaton) exists need not translate into an effective algorithm to find one. We relate our work to the existing literature with a discussion of some known properties ensuring algorithmic solutions, illustrating the ideas over several familiar semirings (including the natural numbers). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_07806 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Feasability of Learning Weighted Automata on a Semiring Daviaud, Laure Johnson, Marianne Formal Languages and Automata Theory Logic in Computer Science Since the seminal work by Angluin and the introduction of the L*-algorithm, active learning of automata by membership and equivalence queries has been extensively studied to learn various extensions of automata. For weighted automata, algorithms for restricted cases have been developed in the literature, but so far there was no global approach or understanding how these algorithms could apply (or not) in the general case. In this paper we chart the boundaries of the Angluin approach. We use a class of hypothesis automata which are constructed, in Angluin's style, by using membership and equivalence queries and solving certain finite systems of linear equations over the semiring, and we show the theoretical limitations of this approach. We classify functions with respect to how guessable they are, corresponding to the existence of hypothesis automata computing a given function, and how such an hypothesis automaton can be found. Of course, from an algorithmic standpoint, knowing that a solution (hypothesis automaton) exists need not translate into an effective algorithm to find one. We relate our work to the existing literature with a discussion of some known properties ensuring algorithmic solutions, illustrating the ideas over several familiar semirings (including the natural numbers). |
| title | Feasability of Learning Weighted Automata on a Semiring |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2309.07806 |