Complexity of the Description Logic ALCM
In this paper we show that the problem of checking consistency of a knowledge base in the Description Logic ALCM is ExpTime-complete. The M stands for meta-modelling as defined by Motz, Rohrer and Severi. To show our main result, we define an ExpTime Tableau algorithm as an extension of an algorithm for checking consistency of a knowledge base in ALC by Nguyen and Szalas.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Alcmean's: Unsupervised community detection using local Laplacian, automatic detection of the number of centers
Community detection is a fundamental problem in the analysis of complex networks. It has applications across social, biological, and financial domains. Traditional algorithms such as Louvain, LPA, and modularity optimiza…
Representation LearningCommunity DetectionALCM: Autonomous LLM-Augmented Causal Discovery Framework
To perform effective causal inference in high-dimensional datasets, initiating the process with causal discovery is imperative, wherein a causal graph is generated based on observational data. However, obtaining a comple…
Causal DiscoveryCausal InferenceAccelerated Algorithms for Source Orientation Detection (AORI) and Spatiotemporal LCMV (ALCMV) Beamforming in EEG Source Localization
This paper illustrates the development of two efficient source localization algorithms for electroencephalography (EEG) data, aimed at enhancing real-time brain signal reconstruction while addressing the computational ch…
EEGContinuous 3D Myocardial Motion Tracking via Echocardiography
Myocardial motion tracking stands as an essential clinical tool in the prevention and detection of cardiovascular diseases (CVDs), the foremost cause of death globally. However, current techniques suffer from incomplete …
Motion EstimationA Parameterized Complexity View on Description Logic Reasoning
Description logics are knowledge representation languages that have been designed to strike a balance between expressivity and computational tractability. Many different description logics have been developed, and numero…