Metrics-Based Incremental Determinization of Finite Automata

Abstract : Some application domains, including monitoring of active systems in artificial intelligence and model-based mutation testing in software engineering, require determinization of finite automata to be performed incrementally. To this end, an algorithm called Incremental Subset Construction (ISC) was proposed a few years ago. However, this algorithm was recently discovered to be incorrect is some instance problems. The incorrect behavior of ISC originates when the redirection of a transition causes a portion of the automaton to be disconnected from the initial state. This misbehavior is disturbing in two ways: portions of the resulting automaton are disconnected and, as such, useless; moreover, a considerable amount of computation is possibly wasted for processing these disconnected parts. To make ISC sound, a metrics-based technique is proposed in this paper, where the distance between states is exploited in order to guarantee the connection of the automaton, thereby allowing ISC to achieve soundness. Experimental results show that, besides being effective, the proposed technique is efficient too.
Type de document :
Communication dans un congrès
Stephanie Teufel; Tjoa A Min; Ilsun You; Edgar Weippl. International Cross-Domain Conference and Workshop on Availability, Reliability, and Security (CD-ARES), Sep 2014, Fribourg, Switzerland. Springer, Lecture Notes in Computer Science, LNCS-8708, pp.29-44, 2014, Availability, Reliability, and Security in Information Systems. 〈10.1007/978-3-319-10975-6_3〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01403984
Contributeur : Hal Ifip <>
Soumis le : lundi 28 novembre 2016 - 11:22:24
Dernière modification le : mardi 29 novembre 2016 - 01:04:51
Document(s) archivé(s) le : mardi 21 mars 2017 - 13:23:29

Fichier

978-3-319-10975-6_3_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Sergiu Balan, Gianfranco Lamperti, Michele Scandale. Metrics-Based Incremental Determinization of Finite Automata. Stephanie Teufel; Tjoa A Min; Ilsun You; Edgar Weippl. International Cross-Domain Conference and Workshop on Availability, Reliability, and Security (CD-ARES), Sep 2014, Fribourg, Switzerland. Springer, Lecture Notes in Computer Science, LNCS-8708, pp.29-44, 2014, Availability, Reliability, and Security in Information Systems. 〈10.1007/978-3-319-10975-6_3〉. 〈hal-01403984〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

16