{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:39:46Z","timestamp":1723016386347},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p>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 \u0141ukasiewicz chain. For each n&gt;1, the logic PD\u0141n is obtained using the n-element \u0141ukasiewicz chain, PDL being equivalent to PD\u01412. 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\u0141n. A generalization of Pratt's exponential-time algorithm for checking validity of formulas is given and EXPTIME-hardness of each PD\u0141n validity problem is established by embedding PDL into PD\u0141n.<\/jats:p>","DOI":"10.24963\/kr.2021\/54","type":"proceedings-article","created":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T16:45:56Z","timestamp":1633970756000},"page":"570-580","source":"Crossref","is-referenced-by-count":0,"title":["Decidability and Complexity of Some Finitely-valued Dynamic Logics"],"prefix":"10.24963","author":[{"given":"Igor","family":"Sedl\u00e1r","sequence":"first","affiliation":[{"name":"Czech Academy of Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"18","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Sea AI Lab","Potassco Solutions","European Association for Artificial Intelligence"],"acronym":"KR-2021","name":"18th International Conference on Principles of Knowledge Representation and Reasoning {KR-2021}","start":{"date-parts":[[2020,11,12]]},"theme":"Artificial Intelligence","location":"Hanoii, Vietnam","end":{"date-parts":[[2021,11,18]]}},"container-title":["Proceedings of the Eighteenth International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T16:46:25Z","timestamp":1633970785000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2021\/54"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2021\/54","relation":{},"subject":[],"published":{"date-parts":[[2021,9]]}}}