Logic Journal of IGPL Advance Access published online on October 29, 2007
Logic Journal of IGPL, doi:10.1093/jigpal/jzm059
Constructing Finite Least Kripke Models for Positive Logic Programs in Serial Regular Grammar Logics
Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland. E-mail: nguyen@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 
t
s1...sk. Such an inclusion axiom corresponds to the grammar rule t s1... sk. Thus the inclusion axioms of L capture a context-free grammar 
. If for every modal index t, the set of words derivable from t using 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 , if M 
then M' .) A least L-model M of P has the property that for every positive formula , P iff M . 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
(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 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. Proceedings of TABLEAUX'1998, LNCS 1397 (1998) 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.
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. In: Proceedings of TABLEAUX 2005, LNAI 3702—Beckert B, ed. (2005) 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. In: Proceedings of IJCAI-05—Kaelbling LP, Saffiotti A, eds. (2005) 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 
. Proceedings of JELIA 2006, LNAI 4160—Fisher M, et al, eds. (2006) 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. In: Proceedings of CLIMA VI, LNAI 3900—Toni F, Torroni P, eds. (2006) Springer-Verlag. 37–56.
25 Nonnengart A. How to use modalities and sorts in Prolog. Proceedings of JELIA'94, LNCS 838—MacNish C, Pearce D, Pereira LM, eds. (1994) Springer. 365–378.
26 Lusk EL, Overbeek RA. A resolution calculus for modal logics. In: Proceedings of CADE-88, LNCS 310 (1988) 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.
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||||