OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Blowout

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,

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

For example:

  (a v b v ~c) ^  (~b v d v ~e)  ^ (~a v c v e) ^ (~c v ~d v ~e)


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.

  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/