Decidability and Complexity of Some Finitely-valued Dynamic Logics

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Decidability and Complexity of Some Finitely-valued Dynamic Logics

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Decidability and Complexity of Some Finitely-valued Dynamic Logics

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GJ18-19162Y" target="_blank" >GJ18-19162Y: Neklasické logické modely informační dynamiky</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

ISBN

978-1-956792-99-7

ISSN

2334-1033

e-ISSN

—

Počet stran výsledku

11

Strana od-do

570-580

Název nakladatele

IJCAI Organization

Místo vydání

Online

Místo konání akce

Hanoi / Online

Datum konání akce

3. 11. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—