Information Technology Reference
In-Depth Information
a
5
b
3
S
1
a
5
b
3
a
a
a
a
a
a
S
1
S
0
S
1
S
2
S
0
S
2
(a) Automaton for
a
(
a
5
b
3
)
∗
a
(b) Automaton for
a
(
a
(
a
5
b
3
)
∗
a
)
∗
a
Fig. 8.
Example automata showing loops and nested repetition
Example 9.
The final example shows the derivation of a constraint from state
S
0
to
S
2
in Figure 8b, which showcases a nested repetition, demonstrating the e
ff
ect of un-
bounded iteration on non-empty modulo sets.
a
(
a
(
a
5
b
3
)
∗
a
)
∗
a
− {∅
2
·
a
,∅
0
·
b
}·
{∅
2
·
a
,∅
0
·
b
}·{∅
5
·
a
,∅
3
·
b
}
∗
∗
Σ
Regex-to-CE, Catenation (7, 9)
)
∗
{∅
2
·
a
,∅
0
·
b
}·
(
{{
5
}
2
·
a
,{
3
}
0
·
b
}
Result of Example 8
{∅
2
·
a
,∅
0
·
b
}·{{
2
,
5
}
0
·
a
,{
3
}
0
·
b
}
Unbounded Repetition (11)
{{
2
,
5
}
2
·
a
,{
3
}
0
·
b
}
Catenation (9)
5
Computational Complexity
The purpose of constraint automata is to determine the precise set of next states for un-
ordered input traces
e
ciently
. Thus, it is important to analyze the computational cost
of using the involved structures.
Consider the conversion of an input automaton
D
, with states
Q
and an alphabet
Σ
. The size of the resultant constraint automaton is
influenced by three factors, namely (i) the
connectivity
of
, into a constraint automaton
CA
D
, with a fully connected au-
tomaton leading to an out-degree of
|
Q
|
for each state in
CA
, thus requiring a maximum
of
constraint expressions to be evaluated with each step in the constraint automa-
ton, (ii) the number of
choice operators
in the regular expressions derived from the
automaton, which a
|
Q
|
ects the number of constraint vectors in the derived constraint ex-
pressions, and (iii) the number of
cycles
in the regular expressions, which will cause
basic constraints' modulo-set sizes to grow.
A sparsely-connected input automaton would tend to have fewer outgoing transitions
per state (as fewer states would be reachable from other states), whereas a densely-
connected automaton containing many loops of di
ff
ering length would increase the size
of constraints' modulo sets. As the constraint vectors in the automaton must be well-
formed, they will each contain
ff
basic constraints.
Furthermore, as the current state is a set of possible states, the set of next states would
have to be computed whilst taking each current state into consideration. The size of the
current state set can be at most
|Σ|
, which would only occur when the automaton is po-
tentially in any state. Hence, the number of operations performed when computing the
|
Q
|
