W3C home > Mailing lists > Public > public-qt-comments@w3.org > March 2005

Re: [FT]FTUnaryNot

From: Chavdar Botev <cbotev@cs.cornell.edu>
Date: Tue, 29 Mar 2005 16:28:32 -0500
Message-ID: <4249C880.3000502@cs.cornell.edu>
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

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 15:45:23 UTC