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 Abstract Freely available
Right arrow Full Text (PDF)
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

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.

References

  1. Balbiani Ph, Fariñas del Cerro L, Herzig A. Declarative semantics for modal logic programs. (1988) Proceedings of the 1988 International Conference on Fifth Generation Computer Systems. ICOT. 507–514.

  2. Baldoni M, Giordano L, Martelli A. A framework for a modal logic programming. In: Joint International Conference and Symposium on Logic Programming. (1996) MIT Press. 52–66.

  3. Baldoni M, Giordano L, Martelli A. A tableau for multimodal logics and some (un)decidability results. (1998) Proceedings of TABLEAUX'1998, LNCS 1397. 44–59.

  4. Cadoli M, Palopoli L, Lenzerini M. Datalog and description logics: Expressive power. DBPL-6, LNCS 1369—Cluet S, Hull R, eds. (1988) Springer. 281–298.

  5. Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R. Data complexity of query answering in description logics. Description Logics 2005—Horrocks I, Sattler U, Wolter F.

  6. Debart F, Enjalbert P, Lescot M. Multimodal logic programming using equational and order-sorted logic. Theoretical Comp. Science (1992) 105:141–166.[CrossRef]

  7. Demri S. The complexity of regularity in grammar logics and related modal logics. Journal of Logic and Computation (2001) 11(6):933–960.[Abstract/Free Full Text]

  8. Demri S, de Nivelle H. Deciding regular grammar logics with converse through first-order logic. Journal of Logic, Language and Information (2005) 14(3):289–329.[CrossRef]

  9. Fariñas del Cerro L, Penttonen M. Grammar logics. Logique et Analyse (1988) 121–122, 123–134.

  10. Goré R, Nguyen LA. A tableau system with automaton-labelled formulae for regular grammar logics. Beckert B, ed. (2005) Proceedings of TABLEAUX 2005, LNAI 3702. Springer-Verlag. 138–152.

  11. Grosof BN, Horrocks I, Volz R, Decker S. Description logic programs: combining logic programs with description logic. WWW (2003) 48–57.

  12. Harel D, Kozen D, Tiuryn J. Dynamic Logic. (2000) MIT Press.

  13. Horrocks I, Sattler U. Decidability of SHIQ with complex role inclusion axioms. Artificial Intelligence (2004) 160(1–2):79–104.[CrossRef][ISI]

  14. Hustadt U, Motik B, Sattler U. Data complexity of reasoning in very expressive description logics. Kaelbling LP, Saffiotti A, eds. (2005) Proceedings of IJCAI-05. Professional Book Center. 466–471.

  15. Konolige K. Belief and incompleteness. Technical Report 319, SRI Inter (1984).

  16. Levy AY, Rousset M-Ch. A representation language combining Hor cription logics. ECAI—Wahlster W, ed. (1996) John Wiley and Sons, Chichester. 323–327.

  17. Mateescu A, Salomaa A. Formal languages: an introduction and a synopsis. In: Handbook of Formal Languages - Volume 1. (1997) Springer. 1–40.

  18. McCarthy J. First order theories of individual concepts and propositions. Machine Intelligence (1979) 9:120–147.

  19. Nguyen LA. Constructing the least models for positive modal logic programs. Fundamenta Informaticae (2000) 42(1):29–60.

  20. Nguyen LA. A fixpoint semantics and an SLD-resolution calculus for modal logic programs. Fundamenta Informaticae (2003) 55(1):63–100.[ISI]

  21. Nguyen LA. A bottom-up method for the deterministic Horn fragment of the description logic Formula . Fisher M, et al, eds. (2006) Proceedings of JELIA 2006, LNAI 4160. Springer-Verlag. 346–358.

  22. Nguyen LA. Multimodal logic programming. Theoretical Computer Science (2006) 360:247–288.[CrossRef][ISI]

  23. Nguyen LA. On the deterministic Horn fragment of test-free PDL. In: Advances in Modal Logic—Volume 6.—Hodkinson I, Venema Y, eds. (2006) King's College Publications. 373–392.

  24. Nguyen LA. Reasoning about epistemic states of agents by modal logic programming. Toni F, Torroni P, eds. (2006) Proceedings of CLIMA VI, LNAI 3900. Springer-Verlag. 37–56.

  25. Nonnengart A. How to use modalities and sorts in Prolog. MacNish C, Pearce D, Pereira LM, eds. (1994) Proceedings of JELIA'94, LNCS 838. Springer. 365–378.

  26. Lusk EL, Overbeek RA. A resolution calculus for modal logics. (1988) Proceedings of CADE-88, LNCS 310. Springer. 500–516.

  27. van Benthem J. Correspondence theory. In: Handbook of Philosophical Logic, Vol II.—Gabbay D, Guenthner F, eds. (1988) Reidel, Dordrecht. 167–247.

  28. Wessel M. Obstacles on the way to qualitative spatial reasoning with description logics: Some undecidability results. Description Logics 2001.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
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?