6533b851fe1ef96bd12a8d12
RESEARCH PRODUCT
Counting in the Two Variable Guarded Logic with Transitivity
Lidia Tenderasubject
Discrete mathematicsTransitive relationGuarded logicTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESFragment (logic)Description logicFunctional predicateTheoryofComputation_LOGICSANDMEANINGSOFPROGRAMSExtension (predicate logic)Undecidable problemMathematicsDecidabilitydescription
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.
year | journal | country | edition | language |
---|---|---|---|---|
2005-01-01 |