Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning.
An important goal of research in description logics (DLs) and related logic-based KR formalisms is to identify the worst-case complexity of reasoning. Such results, however, measure the complexity of a logic as a whole. For example, reasoning in the basic DL is ExpTime-complete, which means that con...
| मुख्य लेखक: | |
|---|---|
| अन्य लेखक: | |
| स्वरूप: | Journal article |
| भाषा: | English |
| प्रकाशित: |
Springer
2012
|
| _version_ | 1826278475382652928 |
|---|---|
| author | Motik, B |
| author2 | Bjørner, N |
| author_facet | Bjørner, N Motik, B |
| author_sort | Motik, B |
| collection | OXFORD |
| description | An important goal of research in description logics (DLs) and related logic-based KR formalisms is to identify the worst-case complexity of reasoning. Such results, however, measure the complexity of a logic as a whole. For example, reasoning in the basic DL is ExpTime-complete, which means that constructors can be used in a way so that exponential time is strictly required for solving a reasoning problem. It is, however, well known that, given two knowledge bases of roughly the same size, reasoning with one knowledge base may be much more difficult than with the other, depending on the interaction of the axioms in the KBs. Thus, existing worst-case complexity results provide only a very coarse measure of reasoning complexity, and they do not tell us much about the "hardness" of each individual knowledge base. © 2012 Springer-Verlag. |
| first_indexed | 2024-03-06T23:44:28Z |
| format | Journal article |
| id | oxford-uuid:706b98f3-789b-4469-a841-2d3136ccb36a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:44:28Z |
| publishDate | 2012 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:706b98f3-789b-4469-a841-2d3136ccb36a2022-03-26T19:37:05ZParameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:706b98f3-789b-4469-a841-2d3136ccb36aEnglishSymplectic Elements at OxfordSpringer2012Motik, BBjørner, NVoronkov, AAn important goal of research in description logics (DLs) and related logic-based KR formalisms is to identify the worst-case complexity of reasoning. Such results, however, measure the complexity of a logic as a whole. For example, reasoning in the basic DL is ExpTime-complete, which means that constructors can be used in a way so that exponential time is strictly required for solving a reasoning problem. It is, however, well known that, given two knowledge bases of roughly the same size, reasoning with one knowledge base may be much more difficult than with the other, depending on the interaction of the axioms in the KBs. Thus, existing worst-case complexity results provide only a very coarse measure of reasoning complexity, and they do not tell us much about the "hardness" of each individual knowledge base. © 2012 Springer-Verlag. |
| spellingShingle | Motik, B Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning. |
| title | Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning. |
| title_full | Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning. |
| title_fullStr | Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning. |
| title_full_unstemmed | Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning. |
| title_short | Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning. |
| title_sort | parameterized complexity and fixed parameter tractability of description logic reasoning |
| work_keys_str_mv | AT motikb parameterizedcomplexityandfixedparametertractabilityofdescriptionlogicreasoning |