Počet záznamů: 1

Decidability and Complexity of Some Finitely-valued Dynamic Logics

SYSNO ASEP	0547245
Druh ASEP	C - Konferenční příspěvek (mezinárodní konf.)
Zařazení RIV	D - Článek ve sborníku
Název	Decidability and Complexity of Some Finitely-valued Dynamic Logics
Tvůrce(i)	Sedlár, Igor (UIVT-O)_{RID, ORCID, SAI}
Zdroj.dok.	Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning. - Online : IJCAI Organization, 2021 / Bienvenu M. ; Lakemeyer G. ; Erdem E. - ISSN 2334-1033 - ISBN 978-1-956792-99-7
Rozsah stran	s. 570-580
Poč.str.	11 s.
Forma vydání	Online - E
Akce	KR2021: International Conference on Principles of Knowledge Representation and Reasoning /18./
Datum konání	03.11.2021 - 12.11.2021
Místo konání	Hanoi / Online
Země	VN - Vietnam
Typ akce	WRD
Jazyk dok.	eng - angličtina
Země vyd.	US - Spojené státy americké
Klíč. slova	reasoning about actions and change ; action languages Uncertainty ; vagueness ; many-valued and fuzzy logics
Vědní obor RIV	BA - Obecná matematika
Obor OECD	Pure mathematics
CEP	GJ18-19162Y GA ČR - Grantová agentura ČR
Institucionální podpora	UIVT-O - RVO:67985807
EID SCOPUS	85126244126
DOI	10.24963/kr.2021/54
Anotace	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.
Pracoviště	Ústav informatiky
Kontakt	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Rok sběru	2022

Počet záznamů: 1