Axiom pinpointing has been introduced in description logics (DL) to help the user understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in question (MinA). Most of the pinpointing algorithms described in the DL literature are obtained as extensions of tableau-based reasoning algorithms for computing consequences from DL knowledge bases. In this paper, we show that automata-based algorithms for reasoning in DLs can also be extended to pinpointing algorithms. The idea is that the tree automaton constructed by the automata-based approach can be transformed into a weighted tree automaton whose so-called behaviour yields a pinpointing formula, i.e., a monotone Boolean formula whose minimal valuations correspond to the MinAs. We also develop an approach for computing the behaviour of a given weighted tree automaton.

Baader, F., Penaloza, R. (2008). Automata-based axiom pinpointing. In Automated Reasoning: 4th International Joint Conference, IJCAR 2008, Sydney, NSW, Australia, August 12-15, 2008, Proceedings (pp.226-241). Springer-Verlag [10.1007/978-3-540-71070-7_19].

Automata-based axiom pinpointing

Penaloza, R
2008

Abstract

Axiom pinpointing has been introduced in description logics (DL) to help the user understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in question (MinA). Most of the pinpointing algorithms described in the DL literature are obtained as extensions of tableau-based reasoning algorithms for computing consequences from DL knowledge bases. In this paper, we show that automata-based algorithms for reasoning in DLs can also be extended to pinpointing algorithms. The idea is that the tree automaton constructed by the automata-based approach can be transformed into a weighted tree automaton whose so-called behaviour yields a pinpointing formula, i.e., a monotone Boolean formula whose minimal valuations correspond to the MinAs. We also develop an approach for computing the behaviour of a given weighted tree automaton.
Si
paper
axiom pinpointing, automata theory, description logics
English
4th International Joint Conference on Automated Reasoning (IJCAR 2008)
978-3-540-71069-1
Baader, F., Penaloza, R. (2008). Automata-based axiom pinpointing. In Automated Reasoning: 4th International Joint Conference, IJCAR 2008, Sydney, NSW, Australia, August 12-15, 2008, Proceedings (pp.226-241). Springer-Verlag [10.1007/978-3-540-71070-7_19].
Baader, F; Penaloza, R
File in questo prodotto:
File Dimensione Formato  
BaPe-IJCAR08.pdf

accesso aperto

Tipologia di allegato: Author’s Accepted Manuscript, AAM (Post-print)
Dimensione 513.25 kB
Formato Adobe PDF
513.25 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/257423
Citazioni
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 11
Social impact