Re: Blowout

[ht@cogsci.ed.ac.uk (Henry S. Thompson)]

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@cogsci.ed.ac.uk
		     URL: http://www.ltg.ed.ac.uk/~ht/