Learning Regular Languages Using RFSA
Abstract
Residual languages are important and natural components of regular languages. Most approaches in grammatical inference rely on this notion. Classical algorithms such as RPNI try to identify prefixes of positive learning examples which give rise to identical residual languages. Here, we study inclusion relations between residual languages. We lead experiments which show that when regular languages are randomly drawn using non deterministicrepresen tations, the number of inclusion relations is very important. We introduced in previous articles a new class of automata which is defined using the notion of residual languages: residual finite state automata (RFSA). RFSA representations of regular languages may have far less states than DFA representations. We prove that RFSA are not polynomially characterizable. However, we design a new learning algorithm, DeLeTe2, based on the search of inclusion relations between residual languages, which produces a RFSA and have both good theoretical properties and good experimental performances.
Cite
Text
Denis et al. "Learning Regular Languages Using RFSA." International Conference on Algorithmic Learning Theory, 2001. doi:10.1007/3-540-45583-3_26Markdown
[Denis et al. "Learning Regular Languages Using RFSA." International Conference on Algorithmic Learning Theory, 2001.](https://mlanthology.org/alt/2001/denis2001alt-learning/) doi:10.1007/3-540-45583-3_26BibTeX
@inproceedings{denis2001alt-learning,
title = {{Learning Regular Languages Using RFSA}},
author = {Denis, François and Lemay, Aurélien and Terlutte, Alain},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2001},
pages = {348-363},
doi = {10.1007/3-540-45583-3_26},
url = {https://mlanthology.org/alt/2001/denis2001alt-learning/}
}