A New Algorithm for Mining Recurrent Rules from a Sequence Database

Mining software specifications is an important research topic, since a software specification is essential for program testing and verification to ensure the correctness of a software. Lo et at. proposed a software specification miner, called BOB, which finds recurrent rules from a sequence database. A recurrent rule has a suitable property to represent temporal notions such as “eventuality” and “regularity” (i.e., always). In BOB, the mining task is realized, among others, by two steps: first generating rule pre/post-conditions and then forming rules by pairing them. This paper proposes a new method, Interleaved Bidirectional Recurrent Rule Miner (iBiRM for short); the idea of the iBiRM algorithm is to interleave the two steps so that intermediate data in the preceding algorithm can be eliminated. It also incorporates a new support counting method tailored to recurrent rule mining to reduce the number of scanning a given database. We also give experimental results, which show that our algorithm improves on the previous approach.