Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce

Abstract Distinguishing sequences are widely used in finite state machine-based conformance testing to solve the state identification problem. In this paper, we address the scalability issue encountered while deriving distinguishing sequences from complete observable nondeterministic finite state ma...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bilal Elghadyry, Faissal Ouardi, Zineb Lotfi, Sébastien Verel
Formato:	article
Lenguaje:	EN
Publicado:	SpringerOpen 2021
Materias:	Conformance test Finite state machines Parallel algorithm MapReduce framework Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/73a721a384aa4cce84bde04ca5e307a5
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:73a721a384aa4cce84bde04ca5e307a5
record_format	dspace
spelling	oai:doaj.org-article:73a721a384aa4cce84bde04ca5e307a52021-11-21T12:02:24ZEfficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce10.1186/s40537-021-00535-62196-1115https://doaj.org/article/73a721a384aa4cce84bde04ca5e307a52021-11-01T00:00:00Zhttps://doi.org/10.1186/s40537-021-00535-6https://doaj.org/toc/2196-1115Abstract Distinguishing sequences are widely used in finite state machine-based conformance testing to solve the state identification problem. In this paper, we address the scalability issue encountered while deriving distinguishing sequences from complete observable nondeterministic finite state machines by introducing a massively parallel MapReduce version of the well-known Exact Algorithm. To the best of our knowledge, this is the first study to tackle this task using the MapReduce approach. First, we give a concise overview of the well-known Exact Algorithm for deriving distinguishing sequences from nondeterministic finite state machines. Second, we propose a parallel algorithm for this problem using the MapReduce approach and analyze its communication cost using Afrati et al. model. Furthermore, we conduct a variety of intensive and comparative experiments on a wide range of finite state machine classes to demonstrate that our proposed solution is efficient and scalable.Bilal ElghadyryFaissal OuardiZineb LotfiSébastien VerelSpringerOpenarticleConformance testFinite state machinesParallel algorithmMapReduce frameworkComputer engineering. Computer hardwareTK7885-7895Information technologyT58.5-58.64Electronic computers. Computer scienceQA75.5-76.95ENJournal of Big Data, Vol 8, Iss 1, Pp 1-27 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Conformance test Finite state machines Parallel algorithm MapReduce framework Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64 Electronic computers. Computer science QA75.5-76.95
spellingShingle	Conformance test Finite state machines Parallel algorithm MapReduce framework Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64 Electronic computers. Computer science QA75.5-76.95 Bilal Elghadyry Faissal Ouardi Zineb Lotfi Sébastien Verel Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce
description	Abstract Distinguishing sequences are widely used in finite state machine-based conformance testing to solve the state identification problem. In this paper, we address the scalability issue encountered while deriving distinguishing sequences from complete observable nondeterministic finite state machines by introducing a massively parallel MapReduce version of the well-known Exact Algorithm. To the best of our knowledge, this is the first study to tackle this task using the MapReduce approach. First, we give a concise overview of the well-known Exact Algorithm for deriving distinguishing sequences from nondeterministic finite state machines. Second, we propose a parallel algorithm for this problem using the MapReduce approach and analyze its communication cost using Afrati et al. model. Furthermore, we conduct a variety of intensive and comparative experiments on a wide range of finite state machine classes to demonstrate that our proposed solution is efficient and scalable.
format	article
author	Bilal Elghadyry Faissal Ouardi Zineb Lotfi Sébastien Verel
author_facet	Bilal Elghadyry Faissal Ouardi Zineb Lotfi Sébastien Verel
author_sort	Bilal Elghadyry
title	Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce
title_short	Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce
title_full	Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce
title_fullStr	Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce
title_full_unstemmed	Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce
title_sort	efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using mapreduce
publisher	SpringerOpen
publishDate	2021
url	https://doaj.org/article/73a721a384aa4cce84bde04ca5e307a5
work_keys_str_mv	AT bilalelghadyry efficientparallelderivationofshortdistinguishingsequencesfornondeterministicfinitestatemachinesusingmapreduce AT faissalouardi efficientparallelderivationofshortdistinguishingsequencesfornondeterministicfinitestatemachinesusingmapreduce AT zineblotfi efficientparallelderivationofshortdistinguishingsequencesfornondeterministicfinitestatemachinesusingmapreduce AT sebastienverel efficientparallelderivationofshortdistinguishingsequencesfornondeterministicfinitestatemachinesusingmapreduce
_version_	1718419312601989120

Efficient parallel derivation of short distinguishing sequences for nondeterministic finite state machines using MapReduce

Ejemplares similares