John, (01)
What I did mention in my note 2 is that there is a field called
"descriptive (expressive) complexity" that has emerged in recent years
that in fact tries to correlate these, i.e., note and gauge the close
correlation between expressing and checking. This goes back to at least
Immerman, in the early 80s, e.g.,
http://www.cs.umass.edu/~immerman/descriptive_complexity.html. (02)
Thanks,
Leo
_____________________________________________
Dr. Leo Obrst The MITRE Corporation, Information Semantics
lobrst@xxxxxxxxx Center for Innovative Computing & Informatics
Voice: 703-983-6770 7515 Colshire Drive, M/S H305
Fax: 703-983-1379 McLean, VA 22102-7508, USA (03)
-----Original Message-----
From: ontology-summit-bounces@xxxxxxxxxxxxxxxx
[mailto:ontology-summit-bounces@xxxxxxxxxxxxxxxx] On Behalf Of John F.
Sowa
Sent: Sunday, January 28, 2007 3:57 PM
To: Ontology Summit 2007 Forum
Subject: Re: [ontology-summit] dimensions/aspects of ontology types? (04)
Leo, (05)
Just one comment about expressivity: (06)
> Expressivity: Expressivity of the semantic model (i.e.,
> underlying knowledge representation language or logic)
> [No scale determined yet] (07)
There are two very important, but widely misunderstood points
about logic: (08)
1. Expressivity of a statement or a theory is independent
of the language in which it is stated. Translation
*never* changes the expressivity. (09)
2. Computational complexity is *not* a result of the
expressivity of any statement, but of the algorithms
used to process that statement. (010)
For example, SQL allows full FOL for queries and constraints, but
the algorithms that process SQL databases are always decidable and
never take more than polynomial time. In fact, many if not most
SQL queries can be evaluated in linear or even logarithmic time. (011)
An example of a logarithmic-time query: (012)
"Find John Doe's department, manager, and job code." (013)
An example of a linear-time query: (014)
"Find all employees who earn more than their managers." (015)
Even highly complex queries can be evaluated very efficiently
if they are only processed on a subset of the database: (016)
"For all employees in department C99, find [Very Complex Query]." (017)
This query may require a polynomial with a large exponent, such as 3.
But if there are only 20 employees in dept. C99, the time would be
proportional to 8,000 -- a trivial number with current hardware. (018)
John (019)
_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/
Subscribe/Config:
http://ontolog.cim3.net/mailman/listinfo/ontology-summit/
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2007/
Community Wiki:
http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2007
Community Portal: http://ontolog.cim3.net/ (020)
_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontology-summit/
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2007/
Community Wiki: http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2007
Community Portal: http://ontolog.cim3.net/ (021)
|