W3C home > Mailing lists > Public > www-tag@w3.org > February 2006

Re: Principle of Least Power

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
Message-ID: <f5bpslxzy7q.fsf@erasmus.inf.ed.ac.uk>

-----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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Thursday, 26 April 2012 12:47:38 GMT