Record link: 
http://hdl.handle.net/20.500.12708/225215
-
Title: 
Guarded Fragments Meet Dynamic Logic: The Story of Regular Guards
en
Citation: 
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.), Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning : Melbourne, Australia. November 11-17, 2025 (pp. 89–99). IJCAI. https://doi.org/10.24963/kr.2025/9
-
Publisher DOI: 
10.24963/kr.2025/9
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Bednarczyk, Bartosz Jan 
Kieroński, Emanuel 
-
Organisational Unit: 
E192-03 - Forschungsbereich Knowledge Based Systems 
-
Published in: 
Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning : Melbourne, Australia. November 11-17, 2025 
-
ISBN: 
978-1-956792-08-9
-
Date (published): 
2025
-
Event name: 
22nd International Conference on Principles of Knowledge Representation and Reasoning 
en
Event date: 
11-Nov-2025 - 17-Nov-2025
-
Event place: 
Melbourne, Australia
-
Number of Pages: 
11
-
Publisher: 
IJCAI
-
Peer reviewed: 
Yes
-
Keywords: 
Decidability; Complexity; Guarded Fragment; Satisfiability Problem; Propositional Dynamic Logic With Intersection And Converse
en
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
Research Areas: 
Computer Science Foundations: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

10
checked on Jan 22, 2026

Google ScholarTM

Check