- Titel
- Standard and Non-Standard Inferences in the Description Logic FL₀ Using Tree Automata
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-796003
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 18-04
- Erstveröffentlichung
- 2018
- DOI
- https://doi.org/10.25368/2022.240
- Abstract (EN)
- Although being quite inexpressive, the description logic (DL) FL₀, which provides only conjunction, value restriction and the top concept as concept constructors, has an intractable subsumption problem in the presence of terminologies (TBoxes): subsumption reasoning w.r.t. acyclic FL₀ TBoxes is coNP-complete, and becomes even ExpTime-complete in case general TBoxes are used. In the present paper, we use automata working on infinite trees to solve both standard and non-standard inferences in FL₀ w.r.t. general TBoxes. First, we give an alternative proof of the ExpTime upper bound for subsumption in FL₀ w.r.t. general TBoxes based on the use of looping tree automata. Second, we employ parity tree automata to tackle non-standard inference problems such as computing the least common subsumer and the difference of FL₀ concepts w.r.t. general TBoxes.
- Freie Schlagwörter (DE)
- Subsumtion, TBox, Beschreibungslogik, strukturelle Charakterisierung, Baumautomat
- Freie Schlagwörter (EN)
- subsumption, TBox, description logic, structural characterization, tree automaton
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Technische Universität Dresden, Dresden
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-796003
- Veröffentlichungsdatum Qucosa
- 20.06.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0