{"id":{"repo_id":"catania","oai_identifier":"oai:www.iris.unict.it:20.500.11769/594343"},"canonical_url":"https://search.dev.ndltd.org/etd/catania/oai:www.iris.unict.it:20.500.11769/594343","repository":{"repo_id":"catania","name":"Università degli Studi di Catania","base_url":"https://www.iris.unict.it/oai/request"},"display":{"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 constructs.","abstract_html":"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 constructs.","abstract_has_math":false,"creators":["LONGO, CRISTIANO"],"institution":"Università degli studi di Catania","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["CANTONE, Domenico"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-12-08","date_published":"2011-12-08","updated_at":"2026-07-24T01:34:49Z","subjects":["Set,Theory,knolwedge,representation,NP-completeness"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess","license:PUBBLICO - Pubblico con Copyright","license uri:iris.PUB02"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/20.500.11769/594343","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Longo, Cristiano","CANTONE, Domenico"]},{"key":"dc:creator","label":"Author","values":["LONGO, CRISTIANO"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-12-08"]},{"key":"dc:publisher","label":"Institution","values":["Università degli studi di Catania","place:Catania"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Set,Theory,knolwedge,representation,NP-completeness"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess","license:PUBBLICO - Pubblico con Copyright","license uri:iris.PUB02"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/20.500.11769/594343"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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 constructs."]},{"key":"dc:title","label":"Title","values":["SET THEORY FOR KNOWLEDGE REPRESENTATION"]}]}],"canonical_facts":{"dc:contributor":["Longo, Cristiano","CANTONE, Domenico"],"dc:creator":["LONGO, CRISTIANO"],"dc:date":["2011-12-08"],"dc:description":["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 constructs."],"dc:identifier":["https://hdl.handle.net/20.500.11769/594343"],"dc:language":["eng"],"dc:publisher":["Università degli studi di Catania","place:Catania"],"dc:rights":["info:eu-repo/semantics/openAccess","license:PUBBLICO - Pubblico con Copyright","license uri:iris.PUB02"],"dc:subject":["Set,Theory,knolwedge,representation,NP-completeness"],"dc:title":["SET THEORY FOR KNOWLEDGE REPRESENTATION"],"dc:type":["info:eu-repo/semantics/doctoralThesis"]},"updated_at":"2026-07-24T01:34:49Z"}