Static API Specification Mining: Exploiting Source Code Model Checking - Mining Software Specifications: Methodologies and Applications - page 121

R1 R2 R3

R4 a a a

b b c d b c c

d d

c e e e

d if if if

e

if

FIGURE 5.3: Four orders R 1 R 2 R 3 R 4 .
s, denoted by sup(s), is the number of strings in SDB that are super-strings
of s.
The transitive closure of a binary relation R is the minimal transitive rela-
tion R 0 that contains R. Thus, (x;y) 2 R provided that there exist z 1 ;:::;z n
such that (x;z 1 ) 2 R, (z n ;y) 2 R, and (z if ;z i+1 ) 2 R for all 1 i < n.
The total order defined by string s = x 1 x l can be written in the tran-
sitive closure of s, denoted by C(s) = f(x if ;x j )j1 i < j lg. Note that,
in the transitive closure, we omit the trivial pairs (xi, if ;x if ). For example, for
string s = abcd, len(s) = 4. The transitive closure is C(s) = f(a;b), (a;c),
(a;d), (b;c), (b;d), (c;d)g. Here, we omit the trivial pairs (a;a), (b;b), (c;c),
and (d;d).
The order containment relation is defined as, for two partial orders R 1 and
R 2 , if R 1 R 2 , then R 1 is said to be weaker than R 2 , and R 2 is stronger than
R 1 . Intuitively, a partially ordered set (or poset for short) satisfying R 2 will
also satisfy R 1 . For example, in Figure 5.3, R 4 R 3 R 2 R 1 . Note that
R 4 covers fewer items than the other three partial orders. Trivially, we can
add the missing items into the DAG as isolated vertices so that every DAG
covers the same set of items. To keep the DAG simple and easy to read, we
omit such isolated items.

5.2.2.2 Frequent Closed Partial Orders (FCPO)

A string database SDB is a multiset of strings. For a partial order R, a
string s is said to support R if R C(s). The support of R in SDB, denoted