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},
}