Decidability and Complexity of Some Finitely-valued Dynamic Logics
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00547245" target="_blank" >RIV/67985807:_____/21:00547245 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.24963/kr.2021/54" target="_blank" >http://dx.doi.org/10.24963/kr.2021/54</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.24963/kr.2021/54" target="_blank" >10.24963/kr.2021/54</a>
Alternative languages
Result language
angličtina
Original language name
Decidability and Complexity of Some Finitely-valued Dynamic Logics
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GJ18-19162Y" target="_blank" >GJ18-19162Y: Non-classical logical models of information dynamics</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning
ISBN
978-1-956792-99-7
ISSN
2334-1033
e-ISSN
—
Number of pages
11
Pages from-to
570-580
Publisher name
IJCAI Organization
Place of publication
Online
Event location
Hanoi / Online
Event date
Nov 3, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—