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

*From*:**ht@cogsci.ed.ac.uk (Henry S. Thompson)***To*: Rick Jelliffe <ricko@allette.com.au>*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@cogsci.ed.ac.uk URL: http://www.ltg.ed.ac.uk/~ht/

**Follow-Ups**:**Re: Blowout***From:*Kohsuke KAWAGUCHI <k-kawa@bigfoot.com>

**Re: Blowout***From:*Murata Makoto <mura034@attglobal.net>

**The devil is always in the detail...***From:*Kohsuke KAWAGUCHI <k-kawa@bigfoot.com>

- 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):