6533b851fe1ef96bd12a8d12

RESEARCH PRODUCT

Counting in the Two Variable Guarded Logic with Transitivity

Lidia Tendera

subject

Discrete mathematicsTransitive relationGuarded logicTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESFragment (logic)Description logicFunctional predicateTheoryofComputation_LOGICSANDMEANINGSOFPROGRAMSExtension (predicate logic)Undecidable problemMathematicsDecidability

description

We show that the extension of the two-variable guarded fragment with transitive guards (GF+TG) by functionality statements is undecidable. This gives immediately undecidability of the extension of GF+TG by counting quantifiers. The result is optimal, since both the three-variable fragment of the guarded fragment with counting quantifiers and the two-variable guarded fragment with transitivity are undecidable. We also show that the extension of GF+TG with functionality, where functional predicate letters appear in guards only, is decidable and of the same complexity as GF+TG. This fragment captures many expressive modal and description logics.

https://doi.org/10.1007/978-3-540-31856-9_7