Using Tableaux and Automata for Pinpointing in EL

From International Center for Computational Logic

Toggle side column

Using Tableaux and Automata for Pinpointing in EL

Rafael PeñalozaRafael Peñaloza
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
  • 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},
}