Information Technology Reference
In-Depth Information
expression
, and is performed by applying the
regex-to-constraint expression
operator
Σ
−
, defined as follows.
Definition 7 (Regex-To-CE).
Given a regular expression
R
, one can derive a con-
straint expression
ˆ
C
, whose vectors are well-formed with respect to an alphabet
Σ
.This
R −
ˆ
ˆ
def
=
is denoted by
C
C = R
Σ
,where
Σ
is defined as:
R
1
R
2
Σ
→ R
1
Σ
· R
2
Σ
R
1
|R
2
Σ
→ R
1
Σ
∨ R
2
Σ
n
Σ
R
∗
Σ
→ R
∗
Σ
n
R
Σ
→ R
a
n
Σ
→{∅
n
·
a
}∪
∅
0
·
e
e
∈Σ\{
a
}
The transformation replaces operators from the regex domain into that of constraint
expressions, and transforms alphabetic symbols into well-formed constraint vectors.
Example 5. a
2
b
{
a
,
b
}
−−−
(
{∅
2
·
a
}∪{∅
0
·
b
}
)
·
(
{∅
1
·
b
}∪{∅
0
·
a
}
)
≡{∅
2
·
a
,∅
0
·
b
}·{∅
0
·
a
,∅
1
·
b
}
4.2 From Constraint Expressions to DCEs
As can be seen in Example 5, the constraint expression produced by
−
will not nec-
essarily be a DCE (in this case, because it contains a concatenation operator), yet the
constraint evaluation function described in Section 3.5 is only defined for DCEs. The
remainder of this section defines the
operator, which must be repeatedly applied to
a constraint expression until a DCE is obtained. Before defining this operator, we first
define the
mod-union
operator
2
N
, as follows:
∪
m
for two sets
M
,
∈
N
def
=
M
∪
m
N
(
M
∪
N
)
\{
m
|
m
,
n
∈
(
M
∪
N
)
,
m
mod
n
=
0
,
m
n
}
When joining two sets under mod-union, values which are divisible by others in the
resultant set are removed. This decreases the number of unnecessary computations that
must be performed by loops, as multiples of values in a modulo set would produce the
same verdict.
Example 6.
The following are two applications of the mod-union operator, the second
of which leads to a reduction in the resultant set.
def
= {
{
}∪
{
}
,
}\{} ≡{
,
}
7
m
3
7
3
7
3
(1)
def
= {
{
}∪
{
}
,
}\{
}≡{
}
3
m
6
3
6
6
3
(2)
Definition 8 (Distribution of Concatenation over Disjunction).
We define
such
that concatenation
distributes
over disjunctions of expressions:
ˆ
C
n
ˆ
C
1
ˆ
C
2
ˆ
C
n
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
C ·
C
1
∨
C
2
∨...∨
C ·
∨
C ·
∨...∨
C ·
Definition 9 (Concatenating Constraints).
Two constraint vectors can be concate-
nated by adding the corresponding basic constraints' o
ff
sets and modulo sets:
(
m
1
∪
m
2
n
2
·
a
∈
C
2
C
1
·
C
2
m
1
n
1
·
a
∈
C
1
,
m
m
2
)
(
n
1
+
n
2
)
·
a
|
a
∈ Σ,
