Re: The Decidability Fetish
Chris and Bill,
I am completely in favor of research on decidability,
complexity, the halting problem, NP completeness, and
analysis of algorithms. I learned a lot from courses
on those topics, and it has been an important part of
my cultural development in logic and comp. sci.
CW> Your choice of words ("fetish") are intentionally
> inflammatory and your arguments can easily be carried
> to imply that complexity in general is completely
> irrelevant. I hope you don't go around telling people
> that understanding the difference between complexity
> classes is not important.
I used the word "fetish" because it is the most precise
term to describe the overhyped ad campaign for the notion
of decidability. See definition #2 from the _American
Heritage Dictionary_:
An object of unreasonably excessive attention or
reverence: _made a fetish of punctuality_.
Thhe quoted question that triggered my note was from
somebody who had been pressured by decidability fetishists
into limiting his choice of logics to satisfy decidability
without regard to any practical application.
As for complexity classes, I believe that they are extremely
important -- far more important, in fact, than the overhyped
issue of decidability. In my note, I pointed out that for
web-scale data, even N-squared complexity is too high.
However, for data *extracted* from the web, the same kinds
of complexity issues apply as for data extracted from any
other source. The word "web" is an irrelevant distraction.
On the following point, Bill and I would agree completely:
CW> For ontologies, expressiveness is key. For SYSTEMS,
> we have to make tradeoffs, and understanding the computational
> properties of a system that requires an ontology helps me
> to tradeoff things like complexity and expressiveness for
> my particualr goals. I find no representation language
> and accompanying reasoner that suits all my needs, I choose
> the right one for the job.
Complexity is a property of applications and the algorithms
that are used. For procedural programming, the most widely
used languages impose no restrictions whatever on expressive
power: their halting properties (i.e., the analog of
decidability) are unprovable, and algorithms of any degree
of complexity ranging from constant time to exponential
and beyond can be expressed in them.
Good programmers who understand complexity issues analyze
the algorithms and don't depend on restrictions in the
languages. Programmers without any formal training learn
cookbook techniques and folklore by trial and error. Both
kinds of people use languages with maximum expressive power.
CW> Your objection, and I suspect Bill's as well, clearly stem
> far more from an over attachment to a particular formalism
> or software, and perhaps a fear of them being eclipsed by OWL,
> than any particularly cogent or objective argument.
My primary attachment is to logic-based systems of all kinds,
at all levels of expressive power for problems of every kind.
I taught courses on logic using several different notations,
including predicate calculus, existential graphs, and CGs.
I also taught courses on Prolog back in the 1980s.
I have been supporting and recommending the work in DLs
since my 1984 book -- but I put them in perspective: they're
useful techniques for certain kinds of problems, and they can
be related to other subsets of logic for other purposes.
My major complaint about OWL is that it's the A-box without
the T-box -- perhaps SWRL may remedy that limitation to some
extent. And the decidability hype is a red herring that
is distracting attention from the more important issue of
different complexity classes for different purposes.
I mostly agree with Bill's comments, but with qualifications:
BA> If you think "ontology" is about how to organize the world
> (of your application), then it's not so clear that you need
> arbitrary recursive power, except to deal with common infinite
> domains (integers, reals and things built from them).
Everything implemented on every computer is finite, but there
are no fixed boundaries. As far as the formalism is concernted,
it's better not to hard-code boundaries of any kind (as we see
whenever we have to change the BIOS to accommodate a bigger disk).
BA> At a minimum you want tabled prolog so prolog-y things that
> ought to terminate do, and the Well-Founded Semantics to allow
> you to express cycles through negation that can't be done in
> tabled prolog. Don't quote me, but I think the folks working
> on SWRL are talking this way, so you may be happy after all.
Yes, I advocated a Horn-clause rule language (Prolog-like) but
added that typed variables and classical negation would be good.
My major complaint about SWRL is that they still pay homage
to the ugly-syntax fetish. From the SWRL document:
Artist(?x) & artistStyle(?x,?y) & Style(?y) & creator(?z,?x)
=> style/period(?z,?y)
Implies(Antecedent(Artist(I-variable(x))
artistStyle(I-variable(x) I-variable(y))
Style(I-variable(y))
creator(I-variable(z) I-variable(x)))
Consequent(style/period(I-variable(z) I-variable(y))))
At the top is acceptable syntax (which I would sweeten by an
optional mapping to Controlled English). Below that is the
semi-uglified syntax, which is designed for translation to the
totally ugly XML version. For more info, see
http://www.daml.org/2003/11/swrl/rules-all.html
SWRL: A Semantic Web Rule Language Combining OWL and RuleML
John