- From: Henry S. Thompson <ht@inf.ed.ac.uk>
- Date: Wed, 08 Feb 2006 15:06:49 +0000
- To: "Bullard, Claude L (Len)" <len.bullard@intergraph.com>
- Cc: "'Dan Connolly'" <connolly@w3.org>, Elliotte Harold <elharo@metalab.unc.edu>, noah_mendelsohn@us.ibm.com, Vincent.Quint@inrialpes.fr, www-tag@w3.org
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 'Expressive' and 'power' are loaded words, what I guess I was asking for was more precision in their use. It's important to keep in mind, for example, that not-Turing-complete does _not_ mean 'safe' or "can't be used for a DoS attack" -- XML DTDs are nowhere near Turing-complete, but, as explained by me [1], the general DTD satisfiability problem is NP-hard none-the-less. The same holds for * RELAX NG with W3C XML Schema Datatypes * Schematron * W3C XML Schema * Namespace Routing Language as explained by Robert Lyons [2]. Another way to put this is that _either_ we should restrict what we say to "avoid Turing-complete languages if you don't need them" _or_ we should be clear about how you measure "power" so you can _tell_ whether language A is or is not less powerful than language B. Worst-case time complexity of the recognition problem would be my first candidate for an appropriate measurement, but I'm not sure whether that applies in all the cases we'd like PLP to cover, or whether it's even _known_ for all the languages we'd like to cover. ht [1] http://aspn.activestate.com/ASPN/Mail/Message/xml-dev/1584981 [2] http://www.mulberrytech.com/Extreme/Proceedings/html/2003/Lyons01/EML2003Lyons01.html - -- Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh Half-time member of W3C Team 2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440 Fax: (44) 131 650-4587, e-mail: ht@inf.ed.ac.uk URL: http://www.ltg.ed.ac.uk/~ht/ [mail really from me _always_ has this .sig -- mail without it is forged spam] -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.6 (GNU/Linux) iD8DBQFD6gkJkjnJixAXWBoRAoKVAJ9uA9uKSfGh9kxfY4ch9FQ76din9ACcDYSD HI3V24ZplGdJpe35IybXwUA= =RlmM -----END PGP SIGNATURE-----
Received on Wednesday, 8 February 2006 15:07:09 UTC