- From: Chavdar Botev <cbotev@cs.cornell.edu>
- Date: Tue, 29 Mar 2005 16:28:32 -0500
- To: andrew.cao@cisra.canon.com.au
- CC: public-qt-comments@w3.org
Hi Andrew!
This is the official response to your question. I am sorry for the late
response.
There has been some confusion with the previous response
<http://lists.w3.org/Archives/Public/public-qt-comments/2005Mar/0068.html>
. Actually, the correct result is neither Result 1 nor Result 2. It is a
little bit more complex. To understand it, it helps to think of the
AllMatches as sentences in Disjunctive Normal Form (DNF). The AllMatches
are disjunctions of the Matches, which are conjunctions of
StringIncludes and StringExcludes. The StringExcludes are negations of
the StringIncludes. If we denote the StringInclude (pos = i) through
SI_i and the StringExclude (pos = i) through SE_i , then your AllMatches
can be written as:
A = (SI_2 \wedge SI_3 \wedge SI_4) \vee (SI_1 \wedge SI_2 \wedge SI_3)
\vee (SI_1 \wedge SI_2 \wedge SI_4) \vee (SI_1 \wedge SI_3 \wedge SI_4)
Thus, to compute FTUnaryNot over A, we simply need to compute \neg A,
transform it into DNF and do the reverse transformation to AllMatches.
In particular,
\neg A = (\neg SI_2 \vee \neg SI_3 \vee \neg SI_4) \wedge (\neg SI_1
\vee \neg SI_2 \vee \neg SI_3) \wedge (\neg SI_1 \vee \neg SI_2 \vee
\neg SI_4) \wedge (\neg SI_1 \vee \neg SI_3 \vee \neg SI_4)
= (SE_2 \vee SE_3 \vee SE_4) \wedge (SE_1 \vee SE_2 \vee SE_3)
\wedge (SE_1 \vee SE_2 \vee SE_4) \wedge (SE_1 \vee SE_3 \vee SE_4)
The transformation back to DNF is straightforward although somehow tedious
\neg A =
(SE_2 \wedge SE_1 \wedge SE_1 \wedge SE_1) \vee
(SE_2 \wedge SE_1 \wedge SE_1 \wedge SE_3) \vee
(SE_2 \wedge SE_1 \wedge SE_1 \wedge SE_4) \vee
(SE_2 \wedge SE_1 \wedge SE_2 \wedge SE_1) \vee
(SE_2 \wedge SE_1 \wedge SE_2 \wedge SE_3) \vee
(SE_2 \wedge SE_1 \wedge SE_2 \wedge SE_4) \vee
(SE_2 \wedge SE_1 \wedge SE_4 \wedge SE_1) \vee
(SE_2 \wedge SE_1 \wedge SE_4 \wedge SE_3) \vee
(SE_2 \wedge SE_1 \wedge SE_4 \wedge SE_4) \vee
(SE_2 \wedge SE_2 \wedge SE_1 \wedge SE_1) \vee
(SE_2 \wedge SE_2 \wedge SE_1 \wedge SE_3) \vee
(SE_2 \wedge SE_2 \wedge SE_1 \wedge SE_4) \vee
(SE_2 \wedge SE_2 \wedge SE_2 \wedge SE_1) \vee
(SE_2 \wedge SE_2 \wedge SE_2 \wedge SE_3) \vee
(SE_2 \wedge SE_2 \wedge SE_2 \wedge SE_4) \vee
(SE_2 \wedge SE_2 \wedge SE_4 \wedge SE_1) \vee
(SE_2 \wedge SE_2 \wedge SE_4 \wedge SE_3) \vee
(SE_2 \wedge SE_2 \wedge SE_4 \wedge SE_4) \vee
(SE_2 \wedge SE_3 \wedge SE_1 \wedge SE_1) \vee
(SE_2 \wedge SE_3 \wedge SE_1 \wedge SE_3) \vee
(SE_2 \wedge SE_3 \wedge SE_1 \wedge SE_4) \vee
(SE_2 \wedge SE_3 \wedge SE_2 \wedge SE_1) \vee
(SE_2 \wedge SE_3 \wedge SE_2 \wedge SE_3) \vee
(SE_2 \wedge SE_3 \wedge SE_2 \wedge SE_4) \vee
(SE_2 \wedge SE_3 \wedge SE_4 \wedge SE_1) \vee
(SE_2 \wedge SE_3 \wedge SE_4 \wedge SE_3) \vee
(SE_2 \wedge SE_3 \wedge SE_4 \wedge SE_4) \vee
(SE_3 \wedge SE_1 \wedge SE_1 \wedge SE_1) \vee
(SE_3 \wedge SE_1 \wedge SE_1 \wedge SE_3) \vee
(SE_3 \wedge SE_1 \wedge SE_1 \wedge SE_4) \vee
(SE_3 \wedge SE_1 \wedge SE_2 \wedge SE_1) \vee
(SE_3 \wedge SE_1 \wedge SE_2 \wedge SE_3) \vee
(SE_3 \wedge SE_1 \wedge SE_2 \wedge SE_4) \vee
(SE_3 \wedge SE_1 \wedge SE_4 \wedge SE_1) \vee
(SE_3 \wedge SE_1 \wedge SE_4 \wedge SE_3) \vee
(SE_3 \wedge SE_1 \wedge SE_4 \wedge SE_4) \vee
(SE_3 \wedge SE_2 \wedge SE_1 \wedge SE_1) \vee
(SE_3 \wedge SE_2 \wedge SE_1 \wedge SE_3) \vee
(SE_3 \wedge SE_2 \wedge SE_1 \wedge SE_4) \vee
(SE_3 \wedge SE_2 \wedge SE_2 \wedge SE_1) \vee
(SE_3 \wedge SE_2 \wedge SE_2 \wedge SE_3) \vee
(SE_3 \wedge SE_2 \wedge SE_2 \wedge SE_4) \vee
(SE_3 \wedge SE_2 \wedge SE_4 \wedge SE_1) \vee
(SE_3 \wedge SE_2 \wedge SE_4 \wedge SE_3) \vee
(SE_3 \wedge SE_2 \wedge SE_4 \wedge SE_4) \vee
(SE_3 \wedge SE_3 \wedge SE_1 \wedge SE_1) \vee
(SE_3 \wedge SE_3 \wedge SE_1 \wedge SE_3) \vee
(SE_3 \wedge SE_3 \wedge SE_1 \wedge SE_4) \vee
(SE_3 \wedge SE_3 \wedge SE_2 \wedge SE_1) \vee
(SE_3 \wedge SE_3 \wedge SE_2 \wedge SE_3) \vee
(SE_3 \wedge SE_3 \wedge SE_2 \wedge SE_4) \vee
(SE_3 \wedge SE_3 \wedge SE_4 \wedge SE_1) \vee
(SE_3 \wedge SE_3 \wedge SE_4 \wedge SE_3) \vee
(SE_3 \wedge SE_3 \wedge SE_4 \wedge SE_4) \vee
(SE_4 \wedge SE_1 \wedge SE_1 \wedge SE_1) \vee
(SE_4 \wedge SE_1 \wedge SE_1 \wedge SE_3) \vee
(SE_4 \wedge SE_1 \wedge SE_1 \wedge SE_4) \vee
(SE_4 \wedge SE_1 \wedge SE_2 \wedge SE_1) \vee
(SE_4 \wedge SE_1 \wedge SE_2 \wedge SE_3) \vee
(SE_4 \wedge SE_1 \wedge SE_2 \wedge SE_4) \vee
(SE_4 \wedge SE_1 \wedge SE_4 \wedge SE_1) \vee
(SE_4 \wedge SE_1 \wedge SE_4 \wedge SE_3) \vee
(SE_4 \wedge SE_1 \wedge SE_4 \wedge SE_4) \vee
(SE_4 \wedge SE_2 \wedge SE_1 \wedge SE_1) \vee
(SE_4 \wedge SE_2 \wedge SE_1 \wedge SE_3) \vee
(SE_4 \wedge SE_2 \wedge SE_1 \wedge SE_4) \vee
(SE_4 \wedge SE_2 \wedge SE_2 \wedge SE_1) \vee
(SE_4 \wedge SE_2 \wedge SE_2 \wedge SE_3) \vee
(SE_4 \wedge SE_2 \wedge SE_2 \wedge SE_4) \vee
(SE_4 \wedge SE_2 \wedge SE_4 \wedge SE_1) \vee
(SE_4 \wedge SE_2 \wedge SE_4 \wedge SE_3) \vee
(SE_4 \wedge SE_2 \wedge SE_4 \wedge SE_4) \vee
(SE_4 \wedge SE_3 \wedge SE_1 \wedge SE_1) \vee
(SE_4 \wedge SE_3 \wedge SE_1 \wedge SE_3) \vee
(SE_4 \wedge SE_3 \wedge SE_1 \wedge SE_4) \vee
(SE_4 \wedge SE_3 \wedge SE_2 \wedge SE_1) \vee
(SE_4 \wedge SE_3 \wedge SE_2 \wedge SE_3) \vee
(SE_4 \wedge SE_3 \wedge SE_2 \wedge SE_4) \vee
(SE_4 \wedge SE_3 \wedge SE_4 \wedge SE_1) \vee
(SE_4 \wedge SE_3 \wedge SE_4 \wedge SE_3) \vee
(SE_4 \wedge SE_3 \wedge SE_4 \wedge SE_4)
=
(SE_1 \wedge SE_2) \vee
(SE_1 \wedge SE_2 \wedge SE_3) \vee
(SE_1 \wedge SE_2 \wedge SE_4) \vee
(SE_1 \wedge SE_2 \wedge SE_3 \wedge SE_4) \vee
(SE_2 \wedge SE_3) \vee
(SE_2 \wedge SE_4) \vee
(SE_2 \wedge SE_3 \wedge SE_4) \vee
(SE_1 \wedge SE_3) \vee
(SE_1 \wedge SE_3 \wedge SE_4) \vee
(SE_3 \wedge SE_4) \vee
(SE_1 \wedge SE_4)
Transforming every SE_i to StringExclude(pos = i) and every conjunction
to a Match produces the final AllMatches.
Thanks,
Chavdar
Received on Tuesday, 29 March 2005 21:28:41 UTC