Quoting "Obrst, Leo J." <lobrst@xxxxxxxxx>: (01)
> There is also the notion of descriptive complexity (under Finite Model
> Theory), which tries to characterize the expressive complexity of
> various logics, i.e., Immerman's chart:
> http://www.cs.umass.edu/~immerman/descriptive_complexity.html (02)
Hi Leo,
I mentioned this is the Ontolog presentation on Thursday. (03)
I suggested an analogue to the programme of descriptive complexity
for restrictions of first-order logic, in which we identify classes of
problems that require the expressiveness of a particular language and
which are not definable in any weaker language. (04)
This can easily be done for the various description logics,
which are explicitly defined with respect to various constructors.
It would be a good idea to identify the classes of problems that
require the expressiveness of FOL and which are not definable in DL.
This shouldn't be too hard, but it would be useful to people who are
trying to find the appropriate language to define their ontology. (05)
>
> It would be nice to factor in Semantic Web languages (and description
> logics) to this. Ian Horrocks has some work in this area. And of
> course, taxonomies, thesauri, and most conceptual models don't have a
> formalization, so it's hard to place them within this framework. (06)
True, but we can still identify the weakest possible language that can
be used to define a particular approach;
for example, taxonomies are definable within monadic FOL. (07)
- michael (08)
_________________________________________________________________
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/ (09)
|