Axiom Dependency Hypergraphs for Fast Modularisation and Atomic Decomposition

Francisco Martin-RecuerdaFrancisco Martin-Recuerda, Dirk WaltherDirk Walther

Download

Francisco Martin-Recuerda, Dirk Walther
Axiom Dependency Hypergraphs for Fast Modularisation and Atomic Decomposition
In Meghyn Bienvenu and Magdalena Ortiz and Riccardo Rosati and Mantas Simkus, eds., Proceedings of the 27th International Workshop on Description Logics (DL'14), volume 1193 of CEUR Workshop Proceedings, 299-310, 2014

Details
Bibtex

KurzfassungAbstract
In this paper we use directed hypergraphs to represent the locality-based dependencies between the axioms of an OWL ontology. We define a notion of an axiom dependency hypergraph, where axioms are represented as nodes and dependencies between axioms as hyper- edges connecting possibly several nodes with one node. We show that a locality-based module of an ontology corresponds to a connected compo- nent in the hypergraph, and an atom of an ontology to a strongly con- nected component. Collapsing the strongly connected components into single nodes yields a condensed axiom dependency hypergraph, which contains the atomic decomposition of the ontology. To condense the ax- iom dependency hypergraph we exploit linear time graph algorithms on its graph fragment. This optimization can significantly reduce the time needed to compute the atomic decomposition of an ontology. We provide an experimental evaluation for computing the atomic decomposition of large biomedical ontologies, and for computing syntactic locality-based modules using the condensed axiom dependency hypergraph.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ MaWa-DL14,
  author = {Francisco {Martin-Recuerda} and Dirk {Walther}},
  booktitle = {Proceedings of the 27th International Workshop on Description Logics ({DL'14})},
  editor = {Meghyn {Bienvenu} and Magdalena {Ortiz} and Riccardo {Rosati} and Mantas {Simkus}},
  pages = {299--310},
  series = {CEUR Workshop Proceedings},
  title = {Axiom Dependency Hypergraphs for Fast Modularisation and Atomic Decomposition},
  volume = {1193},
  year = {2014},
}