ArchivIA - Archivio istituzionale dell'Universita' di Catania >
Tesi di dottorato >
Area 01 - Scienze matematiche e informatiche >
Please use this identifier to cite or link to this item:
|Issue Date: ||23-Feb-2012|
|Authors: ||Longo, Cristiano|
|Title: ||Set theory for knowledge representation|
|Abstract: ||The decision problem in set theory has been intensively
investigated in the last decades, and decision procedures
or proofs of undecidability have been provided for several
quantified and unquantified fragments of set theory.
In this thesis we study the decision problem for three novel
quantified fragments of set theory, which allow the explicit manipulation
of ordered pairs.
We present a decision procedure for each
language of this family, and prove that all of these procedures are optimal (in the sense that they run
in nondeterministic polynomial-time) when restricted to formulae with quantifier
nesting bounded by a constant.
The expressive power of
languages of this family is then measured in terms of set-theoretical
constructs they allow to express. In addition, these languages can
be profitably employed in knowledge representation,
since they allow to express a large amount description logic
|Appears in Collections:||Area 01 - Scienze matematiche e informatiche|
Files in This Item:
|LNGCST79C22C351N-LongoPhdThesis.pdf||LongoPhdThesis||824,57 kB||Adobe PDF||View/Open
Items in ArchivIA are protected by copyright, with all rights reserved, unless otherwise indicated.