Abstract. We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF 2 , which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. This translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. A consequence of the translation is that the general satisfiability problem for regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Using the same method, we show how some other modal logics can be naturally translated into GF 2 , including nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF 2 without extra machinery such as fixed point-operators.
In REF , Demri and de Nivelle gave a translation of the satisfiability problem for grammar logics with converse into the two-variable guarded fragment GF 2 of first-order logic, and showed that the general satisfiability problem for regular grammar logics with converse is in EXPTime.
Deciding regular grammar logics with converse through first-order logic
ArXiv
ArXiv
Computer Science Mathematics