[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] 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, 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/
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|