Decidability and Complexity of Some Finitely-valued Dynamic Logics

0547245 - ÚI 2022 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
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]
Grant CEP: GA ČR(CZ) GJ18-19162Y
Institucionální podpora: RVO:67985807
Klíčová slova: reasoning about actions and change * action languages Uncertainty * vagueness * many-valued and fuzzy logics
Obor OECD: Pure mathematics

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.
Trvalý link: http://hdl.handle.net/11104/0323528