Number of the records: 1  

Decidability and Complexity of Some Finitely-valued Dynamic Logics

  1. 1.
    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

    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

     
     
Number of the records: 1