Results 151 to 160 of about 180 (170)

Guarded Fragments Meet Dynamic Logic: The Story of Regular Guards

Proceedings of the TwentySecond International Conference on Principles of Knowledge Representation and Reasoning
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
Bartosz Bednarczyk, Emanuel Kieronski
openaire   +1 more source

Decidability of the Guarded Fragment with the Transitive Closure

2009
We consider an extension of the guarded fragment in which one can guard quantifiers using the transitive closure of some binary relations. The obtained logic captures the guarded fragment with transitive guards, and in fact extends its expressive power non-trivially, preserving the complexity: we prove that its satisfiability problem is 2Exptime ...
openaire   +1 more source

On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity

2005
We study the finite satisfiability problem for the guarded fragment with transitivity. We prove that in case of one transitive predicate the problem is decidable and its complexity is the same as the general satisfiability problem, i.e. 2Exptime-complete.
Wieslaw Szwast, Lidia Tendera
openaire   +1 more source

Results on the Guarded Fragment with Equivalence or Transitive Relations

2005
We study the problem of the satisfiability of guarded formulas in models in which some distinguished binary symbols are interpreted as equivalence relations or as transitive relations. We sharpen the undecidability result for the two-variable guarded fragment with transitive relations by reducing the number of transitive relations to two. We prove that
openaire   +1 more source

Implementation and Optimisation of a Tableau Algorithm for the Guarded Fragment

2002
In this paper, we present SAGA, the implementation of a tableau-based Satisfiability Algorithm for the Guarded Fragment (GF). Satisfiability for GF with finite signature is ExpTime-complete and therefore theoretically intractable, but existingtableau-based systems for ExpTime-complete description and modal logics perform well for many realistic ...
openaire   +1 more source

A Modal Loosely Guarded Fragment of Second-Order Propositional Modal Logic

Journal of Logic, Language and Information, 2022
Gennady Shtakser
exaly  

EXPSPACE-Complete Variant of Guarded Fragment with Transitivity

2002
We introduce a new fragment GF2 + TG of the first order logic - the two-variable guarded fragment with one-way transitive guards. This logic corresponds in a natural way to temporal logics without past operators. We prove that the satisfiability problem for GF2+TG is EXPSPACE-complete. The lower bound, obtained for the monadic version of the considered
openaire   +1 more source

Guarded counting

2023
Ian Pratt-Hartmann, Pratt-Hartmann Ian
exaly  

Guarded Negation

Journal of the ACM, 2015
Balder Ten Cate, Luc Segoufin, Vince Barany   +2 more
exaly  

Effective Interpolation and Preservation in Guarded Logics

ACM Transactions on Computational Logic, 2016
Michael Benedikt, Balder Ten Cate, Catebalder Ten   +2 more
exaly