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

Re: Blowout

• From: ht@c... (Henry S. Thompson)
• To: Rick Jelliffe <ricko@a...>
• Date: Fri, 02 Mar 2001 21:13:24 +0000

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?

If you can, worst-case complexity is exponential.

3-SAT is: given an expression in conjunctive normal form, where every
conjunct contains exactly 3 terms consisting of a possibly negated
variable, is there a binding of all the variables rendering the whole
true.

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.

Turn this into a language either explicitly (i.e. with an attribute
for negation) or implicitly (use absence for negation) and then try to 
write a (T|R|S) schema.  If you can, assertions about parsers are
beside the point, worst-case complexity is exponential in (n,m) where
is the number of terms and m is the number of variables.

ht
-- 
  Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
          W3C Fellow 1999--2001, part-time member of W3C Team
     2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
	    Fax: (44) 131 650-4587, e-mail: ht@c...
		     URL: http://www.ltg.ed.ac.uk/~ht/

• Follow-Ups:
  • Re: Blowout
    • From: Kohsuke KAWAGUCHI <k-kawa@b...>
  • Re: Blowout
    • From: Murata Makoto <mura034@a...>
  • The devil is always in the detail...
    • From: Kohsuke KAWAGUCHI <k-kawa@b...>

• Prev by Date: RE: is that a fork in the road?
• Next by Date: RE: is that a fork in the road?
• Previous by thread: Re: What is the advantage of RELAX in comparison to Schemas?
• Next by thread: Re: Blowout
• Index(es):
  • Date
  • Thread