Reasoning with prototypes in the description logic ALC using weighted tree automata

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Contributors

Abstract

We introduce an extension to Description Logics that allows us to use prototypes to define concepts. To accomplish this, we introduce the notion of prototype distance functions (pdfs), which assign to each element of an interpretation a distance value. Based on this, we define a new concept constructor of the form P~n(d) for ∼ ∈ {<,≤,>, ≥}, which is interpreted as the set of all elements with a distance ∼ n according to the pdf d. We show how weighted alternating parity tree automata (wapta) over the non-negative integers can be used to define pdfs, and how this allows us to use both concepts and pointed interpretations as prototypes. Finally, we investigate the complexity of reasoning in ALCP(wapta), which extends the Description Logic ALC with the constructors P~n(d) for pdfs defined using wapta.

Details

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications
EditorsBianca Truthe, Jan Janoušek, Adrian-Horia Dediu, Carlos Martín-Vide
PublisherSpringer, Berlin [u. a.]
Pages63-75
Number of pages13
ISBN (print)9783319299990
Publication statusPublished - 2016
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science, Volume 9618
ISSN0302-9743

Conference

Title10th International Conference on Language and Automata Theory and Applications
Abbreviated titleLATA 2016
Conference number10
Duration14 - 18 March 2016
CityPrague
CountryCzech Republic

External IDs

ORCID /0000-0002-4049-221X/work/142247959

Keywords