Inferring DFA without Negative Examples

Florent Avellaneda, Alexandre Petrenko
Proceedings of The 14th International Conference on Grammatical Inference 2018, PMLR 93:17-29, 2019.

Abstract

The inference of a Deterministic Finite Automaton (DFA) without negative examples is one of the most natural inference problems. On the other hand, it is well known that DFA cannot be identified in the limit from positive examples only. We propose two modifications of this problem to make it solvable, i.e., identifiable in the limit, while remaining rather close to the original problem. First, we propose to use the inclusion of languages to reason about complexity and infer the simplest solution. Second, we set the maximum number of states for the inferred DFA. These changes bring new means to control the solution space. While the language inclusion allows us to choose a simplest solution among possible solutions, the maximum number of states determines the degree of approximation. We propose an efficient inference method based on the incremental use of a SAT solver and demonstrate on a practical example the relevance of our approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v93-avellaneda19a, title = {Inferring DFA without Negative Examples}, author = {Avellaneda, Florent and Petrenko, Alexandre}, booktitle = {Proceedings of The 14th International Conference on Grammatical Inference 2018}, pages = {17--29}, year = {2019}, editor = {Unold, Olgierd and Dyrka, Witold and Wieczorek, Wojciech}, volume = {93}, series = {Proceedings of Machine Learning Research}, month = {feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v93/avellaneda19a/avellaneda19a.pdf}, url = {https://proceedings.mlr.press/v93/avellaneda19a.html}, abstract = {The inference of a Deterministic Finite Automaton (DFA) without negative examples is one of the most natural inference problems. On the other hand, it is well known that DFA cannot be identified in the limit from positive examples only. We propose two modifications of this problem to make it solvable, i.e., identifiable in the limit, while remaining rather close to the original problem. First, we propose to use the inclusion of languages to reason about complexity and infer the simplest solution. Second, we set the maximum number of states for the inferred DFA. These changes bring new means to control the solution space. While the language inclusion allows us to choose a simplest solution among possible solutions, the maximum number of states determines the degree of approximation. We propose an efficient inference method based on the incremental use of a SAT solver and demonstrate on a practical example the relevance of our approach.} }
Endnote
%0 Conference Paper %T Inferring DFA without Negative Examples %A Florent Avellaneda %A Alexandre Petrenko %B Proceedings of The 14th International Conference on Grammatical Inference 2018 %C Proceedings of Machine Learning Research %D 2019 %E Olgierd Unold %E Witold Dyrka %E Wojciech Wieczorek %F pmlr-v93-avellaneda19a %I PMLR %P 17--29 %U https://proceedings.mlr.press/v93/avellaneda19a.html %V 93 %X The inference of a Deterministic Finite Automaton (DFA) without negative examples is one of the most natural inference problems. On the other hand, it is well known that DFA cannot be identified in the limit from positive examples only. We propose two modifications of this problem to make it solvable, i.e., identifiable in the limit, while remaining rather close to the original problem. First, we propose to use the inclusion of languages to reason about complexity and infer the simplest solution. Second, we set the maximum number of states for the inferred DFA. These changes bring new means to control the solution space. While the language inclusion allows us to choose a simplest solution among possible solutions, the maximum number of states determines the degree of approximation. We propose an efficient inference method based on the incremental use of a SAT solver and demonstrate on a practical example the relevance of our approach.
APA
Avellaneda, F. & Petrenko, A.. (2019). Inferring DFA without Negative Examples. Proceedings of The 14th International Conference on Grammatical Inference 2018, in Proceedings of Machine Learning Research 93:17-29 Available from https://proceedings.mlr.press/v93/avellaneda19a.html.

Related Material