Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:









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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)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


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section