[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] 3-SAT Re: Blowout
Just to tidy up loose ends. From: Henry S. Thompson <ht@c...> >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? >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. With implicit negation, the Schematron schema fragment is something like: <assert test= " (a or b or not(c)) and (not(b) or d or not(e)) and (not(a) or c or e) and (not(c) or not(d) or not(e))" /> Note that, because we don't have to consume input sequentially against an FSM, there seems no possiblity for explosions or expontiality here. Cheers Rick Jelliffe
|
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
|