OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

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

Re: Blowout

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.