Lu, Chia-Hsuan and Tan, Tony 
ORCID: 0009-0005-8341-2004
(2024)
On two-variable guarded fragment logic with expressive local Presburger constraints.
Logical Methods in Computer Science.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
gp2-lmcs-final.pdf - Author Accepted Manuscript Access to this file is restricted: awaiting official publication and publisher embargo. Download (432kB) |
Abstract
We consider the extension of the two-variable guarded fragment logic with local Presburger quantifiers. These are quantifiers that can express properties such as "the number of incoming blue edges plus twice the number of outgoing red edges is at most three times the number of incoming green edges" and captures various description logics with counting, but without constant symbols. We show that the satisfiability problem for this logic is EXP-complete. While the lower bound already holds for the standard two-variable guarded fragment logic, the upper bound is established by a novel, yet simple deterministic graph-based algorithm.
| Item Type: | Article |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 Apr 2024 07:46 |
| Last Modified: | 15 Apr 2024 08:11 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3180313 |
Share
Share
