<div class="csl-bib-body">
<div class="csl-entry">Bednarczyk, B. J., & Kieroński, E. (2025). Guarded Fragments Meet Dynamic Logic: The Story of Regular Guards. In M. Ortiz, R. Wassermann, & T. Schaub (Eds.), <i>Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning : Melbourne, Australia. November 11-17, 2025</i> (pp. 89–99). IJCAI. https://doi.org/10.24963/kr.2025/9</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/225215
-
dc.description.abstract
We study the Guarded Fragment with Regular Guards RGF which combines the expressive power of the Guarded Fragment (GF) with Propositional Dynamic Logic with Intersection and Converse (ICPDL). Our logic generalizes, in a uniform way, many previously-studied extensions of GF, including (conjunctions of) transitive or equivalence guards, transitive or equivalence closure and more. We prove 2ExpTime-completeness of the satisfiability problem for RGF, showing that RGF is not harder than ICPDL or GF. Shifting to the query entailment problem, we provide undecidability results that significantly strengthen and solidify earlier results along those lines. We conclude by identifying the maximal, in some natural sense, ExpSpace-complete fragment of RGF.
en
dc.language.iso
en
-
dc.subject
Decidability
en
dc.subject
Complexity
en
dc.subject
Guarded Fragment
en
dc.subject
Satisfiability Problem
en
dc.subject
Propositional Dynamic Logic With Intersection And Converse
en
dc.title
Guarded Fragments Meet Dynamic Logic: The Story of Regular Guards
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
University of Wrocław, Poland
-
dc.relation.isbn
978-1-956792-08-9
-
dc.description.startpage
89
-
dc.description.endpage
99
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
2334-1033
-
tuw.booktitle
Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning : Melbourne, Australia. November 11-17, 2025
-
tuw.peerreviewed
true
-
tuw.relation.publisher
IJCAI
-
tuw.researchTopic.id
C5
-
tuw.researchTopic.name
Computer Science Foundations
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-03 - Forschungsbereich Knowledge Based Systems
-
tuw.publisher.doi
10.24963/kr.2025/9
-
dc.description.numberOfPages
11
-
tuw.author.orcid
0000-0002-8267-7554
-
tuw.author.orcid
0000-0002-8538-8221
-
tuw.editor.orcid
0000-0002-2344-9658
-
tuw.event.name
22nd International Conference on Principles of Knowledge Representation and Reasoning
en
tuw.event.startdate
11-11-2025
-
tuw.event.enddate
17-11-2025
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Melbourne
-
tuw.event.country
AU
-
tuw.event.presenter
Bednarczyk, Bartosz Jan
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairetype
conference paper
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.cerifentitytype
Publications
-
item.languageiso639-1
en
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E192-03 - Forschungsbereich Knowledge Based Systems
