Learning Probabilistic Residual Finite Automata
(2002) Grammatical Inference: Algorithms and Applications — ISBN: [3-540-44239-1], p. 77-91, published
Files
LEARNING.pdf
Restricted Access - Adobe PDF
- 254.66 KB
Details
- Authors
- Abstract
- We introduce a new class of probabilistic automata: Probabilistic Residual Finite State Automata. We show that this class can be characterized by a simple intrinsic property of the stochastic languages they generate (the set of residual languages is finitely generated by residuals) and that it admits canonical minimal forms. We prove that there are more languages generated by PRFA than by Probabilistic Deterministic Finite Automata (PDFA). We present a first inference algorithm using this representation and we show that stochastic languages represented by PRFA can be identified from a characteristic sample if words are provided with their probabilities of appearance in the target language.
- Affiliations
Université de Provence, Marseille LIF UMR Université de Lille, France GRAPPA, LIFL
Citations
Esposito, Y., Lemay, A., Denis, F., & Dupont, P. (2002). Learning Probabilistic Residual Finite Automata. In P. Adriaans ; H. Fernau ; M. van Zaanen (ed.), Grammatical Inference: Algorithms and Applications (p. p. 77-91). Springer-Verlag. https://hdl.handle.net/2078.5/254023