Abstract
Hybrid languages have both modal and first-order characteristics: a Kripke semantics, and explicit variable binding apparatus. This paper motivates the development of hybrid languages, sketches their history, and examines the expressive power of three hybrid binders. We show that all three binders give rise to languages strictly weaker than the corresponding first-order language, that full first-order expressivity can be gained by adding the universal modality, and that all three binders can force the existence of infinite models and have undecidable satisfiability problems.
Similar content being viewed by others
References
Alechina, N., 1994, “On one decidable generalised quantifier logic corresponding to a decidable fragment of first-order logic,”Journal of Logic, Language and Information, this issue.
Alechina, N. and Lambalgen, M., 1994, “Correspondence and completeness for generalised quantifiers,” ILLC Technical Note X-94-03, University of Amsterdam.
Allen, J., “Towards a general theory of action and time,”Artificial Intelligence 23, 123–154.
Bird, S. and Blackburn, P., 1991, “A logical approach to arable phonology,” pp. 89–94in Proceedings of the Fifth Conference of the European Chapter of the Association of Computational Linguistics,Berlin.
Blackburn, P., 1993, “Nominal tense logic,”Notre Dame Journal of Formal Logic 14, 56–83.
Blackburn, P., 1994, “Tense, temporal reference, and tense logic,”Journal of Semantics 11, 83–101.
Bull, R., 1970, “An approach to tense logic,”Theoria 36, 282–300.
Buvač, S., Buvač, V. and Mason, I., 1994, “The semantics of prepositional contexts,” pp. 468–477 inProceedings of the Eighth International Symposium on Methodologies for Intelligent System, Lecture Notes for Artificial Intelligence, Berlin: Springer-Verlag.
Buvač, S., Buvač, V. and Mason, I., 1995, “Metamathematics of contexts,”Fundamenta Informaticae 23, 263–301.
Gabbay, D., “An irreflexivity lemma,” pp. 67–89 inAspects of Philosophical Logic, U. Mönnich, ed., Dordrecht: Reidel.
Gargov, G and Goranko, V., 1993, “Modal logic with names,”Journal of Philosophical Logic 22, 607–636.
Goranko, V., 1994, “Temporal logic with reference pointers,” pp. 133–164 inTemporal Logic. First International Conference, ICTL '94 Bonn, Germany, D. Gabbay and H. Ohlbach, eds., Berlin: Springer-Verlag.
Goranko, V., 1995, “Hierarchies of modal and temporal logics with reference pointers,” to appear inJournal of Logic, Language, and Information.
Goranko, V., and Passy, S., 1989, “Using the universal modality: gains and questions,”Journal of Logic and Computation 2, 5–30.
Harel, D., 1983, “Recurring dominoes: making the highly undecidable highly understandable,” pp. 177–194 inSpringer Lecture Notes in Computer Science, Vol.158, Berlin: Springer-Verlag.
Harel, D., 1984, “Dynamic logic,” pp. 497–604 inHandbook of Philosophical Logic, Vol. 2, D. Gabbay and F. Guenthner, eds., Dordrecht: Reidel.
Hodges, W., 1993,Model Theory, Cambridge: Cambridge University Press.
Mcdermott, D., 1982, “A temporal logic for reasoning about processes and plans,”Cognitive Science 6, 101–155.
Passy, S. and Tinchev, T., 1985a, “PDL with data constants,”Information Processing Letters 20, 35–41.
Passy, S. and Tinchev, T., 1985b, “Quantifiers in combinatory PDL: completeness, definability, incompleteness,” pp. 512–519 inSpringer LectureNotes in Computer Science, Vol. 199, Berlin: Springer-Verlag.
Passy, S. and Tinchev, T., 1991, “An essay in combinatory dynamic logic,”Information and Computation 93, 263–332.
Pollard, C. and Sag, I., 1987,Information Based Syntax and Semantics, Volume 1: Fundamentals, Stanford: CSLI.
Prior, A., 1967,Past, Present and Future, Oxford: Oxford University Press.
Prior, A., 1968, “Now”,Nous 2, 101–119.
Reape, M., 1994, “A feature value logic with intensionality, nonwellfoundedness and functional and relational dependencies,” pp. 77–110 inConstraints, Language, and Computation, C.J. Rupp, M. Rosner, and R. Johnson, eds., London: Academic Press.
Rescher, N. and Urquhart, A., 1971,Temporal Logic, New York: Springer-Verlag.
De Rijke, M., 1992a, “The modal logic of inequality,”Journ. Symbolic Logic 57, 566–584.
Richards, B., Bethke, I., van der Does, J., and Oberlander, J., 1989,Temporal Representation and Inference, London: Academic Press.
Seligman, J., 1991, “A cut-free sequent calculus for elementary situated reasoning,” Technical Report HCRC-RP 22, HCRC, Edinburgh.
Seligman, J., 1994, “The logic of correct description,” to appear inAdvances in Intensional Logic, M. de Rijke, ed., Dordrecht: Kluwer.
Seilink, M.P.A., 1994, “Verifying modal formulae over I/O-automata by means of type theory,” Logic Group Preprint Series, Utrecht University.
Van Benthem, J., 1983,Modal Logic and Classical Logic, Napoli: Bibliopolis.
Van Benthem, J., 1984, “Correspondence theory,” pp. 167–247 inHandbook of Philosophical Logic, Vol. 2, D. Gabbay and F. Guenthner, eds., Dordrecht: Reidel.
Van Benthem, J. and Alechina, N., 1994, “Modal quantification over structured domains,” to appear inAdvances in Intensional Logic, M. de Rijke, ed., Dordrecht: Kluwer.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Blackburn, P., Seligman, J. Hybrid languages. J Logic Lang Inf 4, 251–272 (1995). https://doi.org/10.1007/BF01049415
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01049415