Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Concordia University

$30,000.00

Design of optimization techniques and software architectures for description logic reasoners

EF 2015-16

Résumé
The proposed research program is mainly concerned with the design and empirical evaluation of optimization techniques for description logic (DL) reasoners. Over the last decade DL reasoning has gained quite some attention from the semantic web community because the Web Ontology Language, OWL, and its sequel OWL 2 are based on description logics. The DL subset of OWL 2 is a syntactic variant of a well-known and very expressive DL. Roughly speaking DL knowledge is described using concepts, roles, and individuals that can be combined with various constructors. Concepts describe sets of individuals with common properties and roles specify binary relationships between individuals. The concept satisfiability problem for OWL 2 DL is known to be 2-NExpTime-complete. Most reasoners are based on tableau (proof) procedures. The implementation of these calculi requires highly sophisticated optimization techniques due to the structure of the calculi and the inherent time complexity of the inference problems. A large set of tableau optimization techniques needs to be applied to speed up provided inference services and make DL reasoning feasible in practical applications. We propose to continue with our research on the design of optimization techniques and software architectures for DL reasoners with the goal to achieve better scalability even if non-tractable reasoning is required. The major expected outcomes are (i) novel algebraic tableau methods and corresponding optimization techniques that resolve known inefficiencies in standard tableau methods for combinations of OWL 2 DL language features such as qualified cardinality restrictions, nominals, and inverse roles; (ii) new parallel DL reasoning architectures that will support modern multi-processor and multi-core hardware and offer speed improvements that are roughly linear to the number of available cores. The expected outcomes are important for the continued success of ontology development in the semantic web community, especially since the size and complexity of ontologies has often increased in such a way that the time required for (non-tractable) DL reasoning has become a major obstacle.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
261562-2013
Name nom
Haarslev, Volker
Department département
Computer Science and Software Engineering
Organization id
70
Institution établissement
Concordia University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2013
Award amount
30000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2803
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Knowledge representation
Research subject fr
Répresentation des connaissances
Partie
3
Nb partie
5
Application title
Design of optimization techniques and software architectures for description logic reasoners
Keyword
NSERC
Application summary
The proposed research program is mainly concerned with the design and empirical evaluation of optimization techniques for description logic (DL) reasoners. Over the last decade DL reasoning has gained quite some attention from the semantic web community because the Web Ontology Language, OWL, and its sequel OWL 2 are based on description logics. The DL subset of OWL 2 is a syntactic variant of a well-known and very expressive DL. Roughly speaking DL knowledge is described using concepts, roles, and individuals that can be combined with various constructors. Concepts describe sets of individuals with common properties and roles specify binary relationships between individuals. The concept satisfiability problem for OWL 2 DL is known to be 2-NExpTime-complete. Most reasoners are based on tableau (proof) procedures. The implementation of these calculi requires highly sophisticated optimization techniques due to the structure of the calculi and the inherent time complexity of the inference problems. A large set of tableau optimization techniques needs to be applied to speed up provided inference services and make DL reasoning feasible in practical applications. We propose to continue with our research on the design of optimization techniques and software architectures for DL reasoners with the goal to achieve better scalability even if non-tractable reasoning is required. The major expected outcomes are (i) novel algebraic tableau methods and corresponding optimization techniques that resolve known inefficiencies in standard tableau methods for combinations of OWL 2 DL language features such as qualified cardinality restrictions, nominals, and inverse roles; (ii) new parallel DL reasoning architectures that will support modern multi-processor and multi-core hardware and offer speed improvements that are roughly linear to the number of available cores. The expected outcomes are important for the continued success of ontology development in the semantic web community, especially since the size and complexity of ontologies has often increased in such a way that the time required for (non-tractable) DL reasoning has become a major obstacle.