© 1998 by Oxford University Press
Hybrid completeness
Computerlinguistik, Universitat des Saarlandes, 66041 Saarbrucken, Germany A1 Max-Planck-Institut fur Informatik, Im Stadtwald, 66123 Saarbrucken, Germany e-mail: patrick@coli.uni-sb.de e-mail: tzakova@mpi-sb.mpg.de
In this paper we discuss two hybrid languages, 
(A) and (
), and provide them with complete axiomatizations. Both languages combine features of modal and classical logic. Like modal languages, they contain modal operators and have a Kripke semantics. Unlike modal languages, in these systems it is possible to 'label' states by using A and to bind special state variables.
This paper explores the consequences of hybridization for completeness. As we shall show, the challenge is to blend the modal idea of canonical models with the classical idea of witnessed maximal consistent sets. The languages (A) and () provide us with two extreme examples of the issues involved. In the case of (A), we can combine these ideas relatively straightforwardly with the aid of analogs of the Barcan axioms coupled with a modal theory of labeling. In the case of (), on the other hand, although we can still formulate a theory of labeling, the Barcan analogs are not valid. We show how to overcome this difficulty by using COV*, an infinite collection of additional rules of proof which has been used in a number of investigations of extended modal logic (see, for example, Passy and Tinchev [12] and Gargov and Goranko [7]).