Using Tableaux and Automata for Pinpointing in EL

Rafael PeñalozaRafael Peñaloza

Download

Rafael Peñaloza
Using Tableaux and Automata for Pinpointing in EL
In Valentin {Goranko}, eds., TABLEAUX 2009 Wokshop on Tableaux versus Automata as Logical Decision Methods ({AutoTab'09}), 2009

Details
Bibtex

KurzfassungAbstract
We show that the subsumption algorithm for the Description Logic EL can be seen both as a tableau-based and an automata-based decision procedure. Each of these views allows an extension into a so-called pinpointing algorithm. We show that the tableau-based extension has a worst-case exponential execution time, while the automata-based extension runs in polynomial time.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Pena-AT09,
  author = {Rafael {Pe{\~n}aloza}},
  booktitle = {TABLEAUX 2009 Wokshop on Tableaux versus Automata as Logical Decision Methods ({AutoTab'09})},
  editor = {Valentin {Goranko}},
  title = {Using Tableaux and Automata for Pinpointing in EL},
  year = {2009},
}