Information Technology Reference
In-Depth Information
Definition 10 (Bounded Repetition).
The reduction of expressions repeated for a fixed
number of times is defined for a single constraint vector and a disjunction of constraint
expressions, as follows:
m
(
n
×
k
)
·
a
|
C
m
n
·
a
∈
C
k
ˆ
C
n
k
i
1
1
·
i
2
2
· ... ·
i
n
n
ˆ
ˆ
ˆ
ˆ
ˆ
C
1
∨
C
2
∨...∨
C
C
C
i
1
+
i
2
+...+
i
n
=
k
Definition 11 (Unbounded Repetition).
The reduction of expressions within unbounded
repetition is defined for a single constraint vector and a disjunction of constraint expres-
sions, as follows:
(
m
C
∗
m
n
·
a
∈
C
∪
m
{
n
}
)
0
·
a
|
ˆ
C
n
∗
ˆ
C
n
∗
C
1
·
C
2
· ... ·
ˆ
ˆ
ˆ
ˆ
C
1
∨
C
2
∨...∨
4.3
Building the Constraint Automaton
Based on the previous definitions, we can now define a construction for transforming a
finite-state automaton into a constraint automaton.
Definition 12 (Regular Expression to Constraint Expression).
Given a regular ex-
pression
˙
R
,
C
Σ
(
R
)
will return a DCE
C
whose vectors are well-formed with respect to
R −
C
∗
˙
ˆ
Σ
, such that
C
.
def
=
Definition 13 (FSA to CA).
Given a finite-state automaton
D
Q
,
q
0
,Σ,
F
,Γ
with
Q states, initial state q
0
∈
Q, alphabet
Σ
, final states F
⊆
Q, and
Γ ⊆
Q
×Σ ×
Q, one
def
=
CA
,
q
0
,Σ,
,Γ
can construct a constraint automaton
Q
F
,where
(
q
)
˙
˙
Γ
def
=
q
)
q
∈
q
)
,
C,
|
q
,
Q
,R =
regex
D
(
q
,
,R ⊥,
C =C
Σ
(
R
The construction considers each pair of states, deriving the regular expressions and
converting them into constraint expressions. Each state in
will thus have a transition
to every other state with the corresponding constraint expression, provided that a path
between those states exists in
CA
D
.
4.4
Examples
Example 7.
The following example shows the derivation of a constraint from state
S
0
to
S
2
in Figure 7, which involves a repeated set of identical transitions, equivalent to
the bounded iteration of a group of regular expressions related via concatenation. As
with multinomial expansion, raising a DCE with
m
terms to a power
n
will result in a
constraint expression of
n
+
m
−
n
terms. In this example, the terms are reduced further,
yet in general, bounded iteration will produce long DCEs.
