.png){kind=icon}
.png){kind=icon}
Return
Parallel Algorithms for Generating Harmonised State Identifiers and Characterising Sets
.png){kind=icon}
OA
AI
DOI：10.1109/TC.2016.2532869.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Many automated finite state machine (FSM) based test generation algorithms require that a characterising set or a set of harmonised state identifiers is first produced. The only previously published algorithms for partial FSMs were brute-force algorithms with exponential worst case time complexity. This paper presents polynomial time algorithms and also massively parallel implementations of both the polynomial time algorithms and the brute-force algorithms. In the experiments the parallel algorithms scaled better than the sequential algorithms and took much less time. Interestingly, while the parallel version of the polynomial time algorithm was fastest for most sizes of FSMs, the parallel version of the brute-force algorithm scaled better due to lower memory requirements.
Keywords:
Software engineering/software/program verification
software engineering/testing and debugging
software engineering/test design
finite state machine
characterising sets
harmonised state identifiers
general purpose graphics processing units
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K