0547245 - ÚI 2022 RIV US eng C - Conference Paper (international conference)
Sedlár, Igor
Decidability and Complexity of Some Finitely-valued Dynamic Logics.
Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning. Online: IJCAI Organization, 2021 - (Bienvenu, M.; Lakemeyer, G.; Erdem, E.), s. 570-580. ISBN 978-1-956792-99-7. ISSN 2334-1033.
[KR2021: International Conference on Principles of Knowledge Representation and Reasoning /18./. Hanoi / Online (VN), 03.11.2021-12.11.2021]
R&D Projects: GA ČR(CZ) GJ18-19162Y
Institutional support: RVO:67985807
Keywords : reasoning about actions and change * action languages Uncertainty * vagueness * many-valued and fuzzy logics
OECD category: Pure mathematics
DOI: https://doi.org/10.24963/kr.2021/54

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.
Permanent Link: http://hdl.handle.net/11104/0323528