Number of the records: 1
Decidability and Complexity of Some Finitely-valued Dynamic Logics
- 1.
SYSNO ASEP 0547245 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Decidability and Complexity of Some Finitely-valued Dynamic Logics Author(s) Sedlár, Igor (UIVT-O) RID, ORCID, SAI Source Title 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 Pages s. 570-580 Number of pages 11 s. Publication form Online - E Action KR2021: International Conference on Principles of Knowledge Representation and Reasoning /18./ Event date 03.11.2021 - 12.11.2021 VEvent location Hanoi / Online Country VN - Viet Nam Event type WRD Language eng - English Country US - United States Keywords reasoning about actions and change ; action languages Uncertainty ; vagueness ; many-valued and fuzzy logics Subject RIV BA - General Mathematics OECD category Pure mathematics R&D Projects GJ18-19162Y GA ČR - Czech Science Foundation (CSF) Institutional support UIVT-O - RVO:67985807 EID SCOPUS 85126244126 DOI 10.24963/kr.2021/54 Annotation 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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2022
Number of the records: 1