Počet záznamů: 1
Decidability and Complexity of Some Finitely-valued Dynamic Logics
- 1.
SYSNO ASEP 0547245 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Decidability and Complexity of Some Finitely-valued Dynamic Logics Tvůrce(i) Sedlár, Igor (UIVT-O) RID, ORCID, SAI Zdroj.dok. Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning. - Online : IJCAI Organization, 2021 / Bienvenu M. ; Lakemeyer G. ; Erdem E. - ISSN 2334-1033 - ISBN 978-1-956792-99-7 Rozsah stran s. 570-580 Poč.str. 11 s. Forma vydání Online - E Akce KR2021: International Conference on Principles of Knowledge Representation and Reasoning /18./ Datum konání 03.11.2021 - 12.11.2021 Místo konání Hanoi / Online Země VN - Vietnam Typ akce WRD Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova reasoning about actions and change ; action languages Uncertainty ; vagueness ; many-valued and fuzzy logics Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics CEP GJ18-19162Y GA ČR - Grantová agentura ČR Institucionální podpora UIVT-O - RVO:67985807 EID SCOPUS 85126244126 DOI https://doi.org/10.24963/kr.2021/54 Anotace Propositional Dynamic Logic, PDL, is a well known modal logic formalizing reasoning about complex actions. We study many-valued generalizations of PDL based on relational models where satisfaction of formulas in states and accessibility between states via action execution are both seen as graded notions, evaluated in a finite Łukasiewicz chain. For each n>1, the logic PDŁn is obtained using the n-element Łukasiewicz chain, PDL being equivalent to PDŁ2. These finitely-valued dynamic logics can be applied in formalizing reasoning about actions specified by graded predicates, reasoning about costs of actions, and as a framework for certain graded description logics with transitive closure of roles. Generalizing techniques used in the case of PDL we obtain completeness and decidability results for all PDŁn. A generalization of Pratt's exponential-time algorithm for checking validity of formulas is given and EXPTIME-hardness of each PDŁn validity problem is established by embedding PDL into PDŁn. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2022
Počet záznamů: 1