[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

3-SAT Re: Blowout

• From: Rick Jelliffe <ricko@a...>
• To: xml-dev@l...
• Date: Thu, 15 Mar 2001 11:53:06 +0800

Just to tidy up loose ends.

From: Henry S. Thompson <ht@c...>

>I'm curious as to the collective wisdom wrt the usual (in
>computational linguistics) way of checking the worst-case complexity
>of grammar formalisms:  can you encode 3-SAT in TREX, RELAX,
>Schematron?

>For example:
>
>  (a v b v ~c) ^  (~b v d v ~e)  ^ (~a v c v e) ^ (~c v ~d v ~e)
>
>a=1
>b=0
>c=1
>d=0
>e=1
>
>satisfies this.

With implicit negation, the Schematron schema fragment is something like:

<assert test=
  " (a or b or not(c)) and
     (not(b) or d or not(e)) and
     (not(a) or c or e) and
     (not(c) or not(d) or not(e))" />

Note that, because we don't have to consume input sequentially against an
FSM, there seems no possiblity for explosions or expontiality here.

Cheers
Rick Jelliffe

• Prev by Date: RE: A simple guy with a simple problem
• Next by Date: Re: Schemas and Semantics (was: A Personal Reply...)
• Previous by thread: Re: Names, Nmtokens, and Namespaces
• Next by thread: XML Encoding of XPath: DTD
• Index(es):
  • Date
  • Thread