Inferring Non-resettable Mealy Machines with $n$ States

Roland Groz, Catherine Oriat, Nicolas Brémond
Proceedings of The 13th International Conference on Grammatical Inference, PMLR 57:30-41, 2017.

Abstract

Automata inference algorithms are used to extract behavioural models of software components. However, when the software system cannot be reset, inference must be done from a single trace. This paper proposes an active learning algorithm that can infer a Mealy model under the assumption that the number of the states of the machine is known and that a characterization set for it is provided. This algorithm improves on a previous paper that used a looser assumption on the number of states. The complexity is polynomial in the number of states of the Mealy machine.

Cite this Paper


BibTeX
@InProceedings{pmlr-v57-groz16, title = {Inferring Non-resettable {M}ealy Machines with $n$ States}, author = {Groz, Roland and Oriat, Catherine and Brémond, Nicolas}, booktitle = {Proceedings of The 13th International Conference on Grammatical Inference}, pages = {30--41}, year = {2017}, editor = {Verwer, Sicco and Zaanen, Menno van and Smetsers, Rick}, volume = {57}, series = {Proceedings of Machine Learning Research}, address = {Delft, The Netherlands}, month = {05--07 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v57/groz16.pdf}, url = {http://proceedings.mlr.press/v57/groz16.html}, abstract = {Automata inference algorithms are used to extract behavioural models of software components. However, when the software system cannot be reset, inference must be done from a single trace. This paper proposes an active learning algorithm that can infer a Mealy model under the assumption that the number of the states of the machine is known and that a characterization set for it is provided. This algorithm improves on a previous paper that used a looser assumption on the number of states. The complexity is polynomial in the number of states of the Mealy machine.} }
Endnote
%0 Conference Paper %T Inferring Non-resettable Mealy Machines with $n$ States %A Roland Groz %A Catherine Oriat %A Nicolas Brémond %B Proceedings of The 13th International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2017 %E Sicco Verwer %E Menno van Zaanen %E Rick Smetsers %F pmlr-v57-groz16 %I PMLR %P 30--41 %U http://proceedings.mlr.press/v57/groz16.html %V 57 %X Automata inference algorithms are used to extract behavioural models of software components. However, when the software system cannot be reset, inference must be done from a single trace. This paper proposes an active learning algorithm that can infer a Mealy model under the assumption that the number of the states of the machine is known and that a characterization set for it is provided. This algorithm improves on a previous paper that used a looser assumption on the number of states. The complexity is polynomial in the number of states of the Mealy machine.
RIS
TY - CPAPER TI - Inferring Non-resettable Mealy Machines with $n$ States AU - Roland Groz AU - Catherine Oriat AU - Nicolas Brémond BT - Proceedings of The 13th International Conference on Grammatical Inference DA - 2017/01/16 ED - Sicco Verwer ED - Menno van Zaanen ED - Rick Smetsers ID - pmlr-v57-groz16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 57 SP - 30 EP - 41 L1 - http://proceedings.mlr.press/v57/groz16.pdf UR - http://proceedings.mlr.press/v57/groz16.html AB - Automata inference algorithms are used to extract behavioural models of software components. However, when the software system cannot be reset, inference must be done from a single trace. This paper proposes an active learning algorithm that can infer a Mealy model under the assumption that the number of the states of the machine is known and that a characterization set for it is provided. This algorithm improves on a previous paper that used a looser assumption on the number of states. The complexity is polynomial in the number of states of the Mealy machine. ER -
APA
Groz, R., Oriat, C. & Brémond, N.. (2017). Inferring Non-resettable Mealy Machines with $n$ States. Proceedings of The 13th International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 57:30-41 Available from http://proceedings.mlr.press/v57/groz16.html.

Related Material