Induction of Non-Deterministic Finite Automata on Supercomputers

Wojciech Wieczorek
Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:237-242, 2012.

Abstract

The problem of inducing automata of minimal size consistent with finite sets of examples and counter-examples is the combinatorial optimization task of grammatical inference and is known to be computationally hard. Both an exact and a heuristic method of finding a non-deterministic finite automaton (NFA) with a given number of states such that all examples are accepted and all counter-examples are rejected by the automaton will be evaluated. The methods are based on a translation of NFA identification into integer nonlinear programming.

Cite this Paper

BibTeX
@InProceedings{pmlr-v21-wieczorek12a, title = {Induction of Non-Deterministic Finite Automata on Supercomputers}, author = {Wieczorek, Wojciech}, booktitle = {Proceedings of the Eleventh International Conference on Grammatical Inference}, pages = {237--242}, year = {2012}, editor = {Heinz, Jeffrey and Higuera, Colin and Oates, Tim}, volume = {21}, series = {Proceedings of Machine Learning Research}, address = {University of Maryland, College Park, MD, USA}, month = {05--08 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v21/wieczorek12a/wieczorek12a.pdf}, url = {https://proceedings.mlr.press/v21/wieczorek12a.html}, abstract = {The problem of inducing automata of minimal size consistent with finite sets of examples and counter-examples is the combinatorial optimization task of grammatical inference and is known to be computationally hard. Both an exact and a heuristic method of finding a non-deterministic finite automaton (NFA) with a given number of states such that all examples are accepted and all counter-examples are rejected by the automaton will be evaluated. The methods are based on a translation of NFA identification into integer nonlinear programming.} }
Endnote
%0 Conference Paper %T Induction of Non-Deterministic Finite Automata on Supercomputers %A Wojciech Wieczorek %B Proceedings of the Eleventh International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2012 %E Jeffrey Heinz %E Colin Higuera %E Tim Oates %F pmlr-v21-wieczorek12a %I PMLR %P 237--242 %U https://proceedings.mlr.press/v21/wieczorek12a.html %V 21 %X The problem of inducing automata of minimal size consistent with finite sets of examples and counter-examples is the combinatorial optimization task of grammatical inference and is known to be computationally hard. Both an exact and a heuristic method of finding a non-deterministic finite automaton (NFA) with a given number of states such that all examples are accepted and all counter-examples are rejected by the automaton will be evaluated. The methods are based on a translation of NFA identification into integer nonlinear programming.
RIS
TY - CPAPER TI - Induction of Non-Deterministic Finite Automata on Supercomputers AU - Wojciech Wieczorek BT - Proceedings of the Eleventh International Conference on Grammatical Inference DA - 2012/08/16 ED - Jeffrey Heinz ED - Colin Higuera ED - Tim Oates ID - pmlr-v21-wieczorek12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 21 SP - 237 EP - 242 L1 - http://proceedings.mlr.press/v21/wieczorek12a/wieczorek12a.pdf UR - https://proceedings.mlr.press/v21/wieczorek12a.html AB - The problem of inducing automata of minimal size consistent with finite sets of examples and counter-examples is the combinatorial optimization task of grammatical inference and is known to be computationally hard. Both an exact and a heuristic method of finding a non-deterministic finite automaton (NFA) with a given number of states such that all examples are accepted and all counter-examples are rejected by the automaton will be evaluated. The methods are based on a translation of NFA identification into integer nonlinear programming. ER -
APA
Wieczorek, W.. (2012). Induction of Non-Deterministic Finite Automata on Supercomputers. Proceedings of the Eleventh International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 21:237-242 Available from https://proceedings.mlr.press/v21/wieczorek12a.html.

Related Material