Skip Navigation


Logic Journal of IGPL Advance Access originally published online on October 29, 2007
Logic Journal of IGPL 2008 16(2):175-193; doi:10.1093/jigpal/jzm059
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
16/2/175    most recent
jzm059v1
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Nguyen, L. A.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2007. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Constructing Finite Least Kripke Models for Positive Logic Programs in Serial Regular Grammar Logics

Linh Anh Nguyen

Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland. E-mail: nguyen{at}mimuw.edu.pl


  Abstract

A serial context-free grammar logic is a normal multimodal logic L characterized by the seriality axioms and a set of inclusion axioms of the form {square}t{varphi}->{square}s1...{square}sk{varphi}. Such an inclusion axiom corresponds to the grammar rule t -> s1... sk. Thus the inclusion axioms of L capture a context-free grammar Formula. If for every modal index t, the set of words derivable from t using Formula is a regular language, then L is a serial regular grammar logic.

In this paper, we present an algorithm that, given a positive multimodal logic program P and a set of finite automata specifying a serial regular grammar logic L, constructs a finite least L-model of P. (A model M is less than or equal to model M' if for every positive formula {varphi}, if M models {varphi} then M' models {varphi}.) A least L-model M of P has the property that for every positive formula {varphi}, P models {varphi} iff M models {varphi}. The algorithm runs in exponential time and returns a model with size 2O(n3). We give examples of P and L, for both of the case when L is fixed or P is fixed, such that every finite least L-model of P must have size 2{Omega}(n). We also prove that if G is a context-free grammar and L is the serial grammar logic corresponding to G then there exists a finite least L-model of {square}s p iff the set of words derivable from s using G is a regular language.

Key Words: modal logic • Horn logic • model construction

Received for publication 25 November 2006.
Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.