Chia-Hsuan Lu ; Tony Tan - On two-variable guarded fragment logic with expressive local Presburger constraints

lmcs:9757 - Logical Methods in Computer Science, August 27, 2024, Volume 20, Issue 3 - https://doi.org/10.46298/lmcs-20(3:16)2024
On two-variable guarded fragment logic with expressive local Presburger constraintsArticle

Authors: Chia-Hsuan Lu ORCID; Tony Tan ORCID

    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.

    https://doi.org/10.46298/lmcs-20(3:16)2024
    Source: arXiv.org:2206.13731
    Volume: Volume 20, Issue 3
    Published on: August 27, 2024
    Accepted on: April 5, 2024
    Submitted on: July 1, 2022
    Keywords: Computer Science - Logic in Computer Science
    Licence: Attribution 4.0 International (CC BY 4.0)

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    Share and export

    Consultation statistics

    This page has been seen 815 times.
    This article's PDF has been downloaded 268 times.