Parallel Algorithm for Approximate State Graph Exploration With Restricted Memory Footprint

ABSTRACT We investigate the performance of algorithms that explore large state graphs of finite state machines without input by following paths. To improve on anchor‐based and candidate‐based explorations and to avoid the performance overhead of full anchor lists and the tuning sensitivity of timeout‐based methods, we propose and analyze exploration based on two combinations: two sets of candidate nodes and candidate nodes plus a restricted form of anchors. We confirm our analysis by experiments on a multicore machine: both combinations achieve similar performance, with slight differences depending on the input graph and with respect to accuracy of secondary information like the point of entry into the cycle. The method with two candidate sets provides accurate information also on the tail length, while the method with candidates and restricted anchors often yields best performance.