• From: Murata Makoto <mura034@a...>
• To: xml-dev@x...
• Date: Sun, 04 Mar 2001 21:19:11 +0900

xml-dev-digest-errors@l... 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@c... (Henry S. Thompson)

• Prev by Date: Re: We need an XPath API
• Next by Date: Re: We need an XPath API
• Previous by thread: Re: Blowout
• Next by thread: The devil is always in the detail...
• Index(es):
  • Date
  • Thread