Inferring FSM Models of Systems Without Reset
| Autor: | Alexandre Petrenko, Adenilso Simao, Roland Groz, Catherine Oriat |
|---|---|
| Přispěvatelé: | Université Grenoble Alpes INP (Grenoble INP), Universidade de São Paulo (USP), Centre de Recherche Informatique de Montréal = Computer Research Institute of Montréal (CRIM), Validation de Systèmes, Composants et Objets logiciels (VASCO), Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Polynomial
Sequence Computer science Inference 020207 software engineering 02 engineering and technology [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] Oracle Set (abstract data type) Cardinality 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Equivalence (measure theory) Reset (computing) Algorithm ComputingMilieux_MISCELLANEOUS |
| Zdroj: | Machine Learning for Dynamic Software Analysis Machine Learning for Dynamic Software Analysis, pp.178-201, 2018 Lecture Notes in Computer Science ISBN: 9783319965611 |
| Popis: | Active inference algorithms that are used to extract behavioural models of software systems usually assume that the System Under Inference (SUI) can be reset. Two approaches have been proposed to infer systems that cannot be reset. Rivest and Schapire proposed an adaptation of the \(L^*\) algorithm that relies on having a homing sequence for the SUI. We detail here another approach that is based on characterization sequences. More precisely, we assume classical testing hypotheses, namely that we are given a bound n on the number of states and a set W of characterizing sequences to distinguish states. Contrary to \(L^*\), it does not require an external oracle to decide on equivalence. The length of the test sequence is polynomial in n and the exponent depends on the cardinality |W| of the characterization set. For systems where resetting is impossible or expensive, this approach can be a viable alternative to classical learning methods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|