Publications: Report

Technical, Research Report
@TechReport
Technischer-, Forschungsbericht

Show entries of:

this year (2024) | last year (2023) | two years ago (2022) | Notes URL

Action:

Options:

Goto entry point

Author, Editor

Author(s):

de Nivelle, Hans
Demri, Stéphane

dblp
dblp

Not MPG Author(s):

Demri, Stéphane

Editor(s):

BibTeX Citekey*:	deNivelleDemri2003a
Language:	English

Title, Institution

Title*:	Deciding regular grammar logics with converse through first-order logic
Institution*:	Laboratoire de Spécification et de Vérification, ENS Cachan
Publishers or Institutions Address*:	Cachan, France
Type:	research report

No, Year, pp.,

Number*:	LSV-03-4	Pages*:	29
Month:		VG Wort Pages*:
Year*:	2003	ISBN/ISSN:

DOI:

Note, Abstract, ©

Note:
(LaTeX) Abstract:	We provide a simple translation of the satisfiability problem for grammar logics with converse into GF2 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 GF2, 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 GF2 without extra machinery such as fixed point-operators. This answers an open question posed in [Demri'01].
Categories / Keywords:	modal logic, theorem proving
Copyright Message:
HyperLinks / References / URLs:
Personal Comments:
File Upload:
Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Programming Logics Group
Audience:	experts only
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort, CCL bibliography

BibTeX Entry:

@TECHREPORT{deNivelleDemri2003a,
AUTHOR = {de Nivelle, Hans and Demri, St{\'e}phane},
TITLE = {Deciding regular grammar logics with converse through first-order logic},
YEAR = {2003},
TYPE = {research report},
INSTITUTION = {Laboratoire de Spécification et de Vérification, ENS Cachan},
NUMBER = {LSV-03-4},
PAGES = {29},
ADDRESS = {Cachan, France},
}

Entry last modified by Hans de Nivelle, 01/28/2008

Edit History (please click the blue arrow to see the details)

	Editor(s) Hans de Nivelle	Created 01/26/2004 01:40:21 PM
Revision 1. 0.	Editor Hans de Nivelle Hans de Nivelle	Edit Date 01/29/2004 10:58:49 AM 01/26/2004 01:40:21 PM

Attachment Section