[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Blowout
- From: Murata Makoto <mura034@attglobal.net>
- To: xml-dev@xml.org
- Date: Sun, 04 Mar 2001 21:19:11 +0900
xml-dev-digest-errors@lists.xml.org wrote:
>
> 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?
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.
Cheers,
Makoto
- References:
- Re: Blowout
- From: ht@cogsci.ed.ac.uk (Henry S. Thompson)