Query Learning Algorithm for Symbolic Weighted Finite Automata

Kaito Suzuki, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara
Proceedings of the Fifteenth International Conference on Grammatical Inference, PMLR 153:202-216, 2021.

Abstract

We propose a query learning algorithm for an extension of weighted finite automata (WFAs), named symbolic weighted finite automata (SWFAs), which can handle strings over infinite alphabets more efficiently. Based on the idea of symbolic finite automata, SWFAs generalize WFAs by allowing transitions to be functions from a possibly infinite alphabet to weights. Our algorithm can learn SWFAs if functions in transitions are also learnable by queries. We also investigate minimization and equivalence checking for SWFAs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v153-suzuki21a, title = {Query Learning Algorithm for Symbolic Weighted Finite Automata}, author = {Suzuki, Kaito and Hendrian, Diptarama and Yoshinaka, Ryo and Shinohara, Ayumi}, booktitle = {Proceedings of the Fifteenth International Conference on Grammatical Inference}, pages = {202--216}, year = {2021}, editor = {Chandlee, Jane and Eyraud, Rémi and Heinz, Jeff and Jardine, Adam and van Zaanen, Menno}, volume = {153}, series = {Proceedings of Machine Learning Research}, month = {23--27 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v153/suzuki21a/suzuki21a.pdf}, url = {https://proceedings.mlr.press/v153/suzuki21a.html}, abstract = {We propose a query learning algorithm for an extension of weighted finite automata (WFAs), named symbolic weighted finite automata (SWFAs), which can handle strings over infinite alphabets more efficiently. Based on the idea of symbolic finite automata, SWFAs generalize WFAs by allowing transitions to be functions from a possibly infinite alphabet to weights. Our algorithm can learn SWFAs if functions in transitions are also learnable by queries. We also investigate minimization and equivalence checking for SWFAs.} }
Endnote
%0 Conference Paper %T Query Learning Algorithm for Symbolic Weighted Finite Automata %A Kaito Suzuki %A Diptarama Hendrian %A Ryo Yoshinaka %A Ayumi Shinohara %B Proceedings of the Fifteenth International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2021 %E Jane Chandlee %E Rémi Eyraud %E Jeff Heinz %E Adam Jardine %E Menno van Zaanen %F pmlr-v153-suzuki21a %I PMLR %P 202--216 %U https://proceedings.mlr.press/v153/suzuki21a.html %V 153 %X We propose a query learning algorithm for an extension of weighted finite automata (WFAs), named symbolic weighted finite automata (SWFAs), which can handle strings over infinite alphabets more efficiently. Based on the idea of symbolic finite automata, SWFAs generalize WFAs by allowing transitions to be functions from a possibly infinite alphabet to weights. Our algorithm can learn SWFAs if functions in transitions are also learnable by queries. We also investigate minimization and equivalence checking for SWFAs.
APA
Suzuki, K., Hendrian, D., Yoshinaka, R. & Shinohara, A.. (2021). Query Learning Algorithm for Symbolic Weighted Finite Automata. Proceedings of the Fifteenth International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 153:202-216 Available from https://proceedings.mlr.press/v153/suzuki21a.html.

Related Material