Using Tableaux and Automata for Pinpointing in EL

PublikationenPublications

• Nach AutorBy Author
  • Rafael Peñaloza NyssenRafael Peñaloza Nyssen
• Nach ForschungsgruppeBy Research Group
  • AutomatentheorieAutomata Theory

Toggle side column

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