[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
- From: Murata Makoto <email@example.com>
- To: firstname.lastname@example.org
- Date: Sun, 04 Mar 2001 21:19:11 +0900
> 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,
Both RELAX and TREX take time linear to the size of the instance.
To each element, we have to assign a set of non-terminals. This assignment
is performed from leaf nodes to the root node. That's all.
- Re: Blowout
- From: email@example.com (Henry S. Thompson)