We introduce and study hierarchies of extensions of the propositional modal and temporal languages with pairs of new syntactic devices: point of reference-reference pointer which enable semantic references to be made within a formula. We propose three different but equivalent semantics for the extended languages, discuss and compare their expressiveness. The languages with reference pointers are shown to have great expressive power (especially when their frugal syntax is taken into account), perspicuous semantics, and simple deductive systems. For instance, Kamp's and (...) Stavi's temporal operators, as well as nominals (names, clock variables), are definable in them. Universal validity in these languages is proved undecidable. The basic modal and temporal logics with reference pointers are uniformly axiomatized and a strong completeness theorem is proved for them and extended to some classes of their extensions. (shrink)

In their simplest form, hybrid languages are propositional modal languages which can refer to states. They were introduced by Arthur Prior, the inventor of tense logic, and played an important role in his work: because they make reference to specific times possible, they remove the most serious obstacle to developing modal approaches to temporal representation and reasoning. However very little is known about the computational complexity of hybrid temporal logics.In this paper we analyze the complexity of the satisfiability problem of (...) a number of hybrid temporal logics: the basic hybrid language over transitive trees; nominal Until logic; and referential interval logic. We discuss the effects of including nominals, the @ operator, the somewhere modality E, and the difference operator D. Adding nominals to tense logic leads for several frame-classes to an increase in complexity of the satisfiability problem from PSPACE to EXPTIME. On transitive trees, however, the satisfiability problem for this language can be decided in PSPACE. Along the way we make a detour through hybrid propositional dynamic logic: we establish upper bounds for a number of temporal logics by generalizing results due to Passy and Tinchev [29] and De Giacomo [16]. We conclude with some remarks on the relevance of our results to description logic, and draw attention to the utility of the spypoint technique for proving upper and lower bounds. (shrink)

The author's motivation for constructing the calculi of this paper\nis so that time and tense can be "discussed together in the same\nlanguage" (p. 282). Two types of enriched propositional caluli for\ntense logic are considered, both containing ordinary propositional\nvariables for which any proposition may be substituted. One type\nalso contains "clock-propositional" variables, a,b,c, etc., for\nwhich only clock-propositional variables may be substituted and that\ncorrespond to instants or moments in the semantics. The other type\nalso contains "history-propositional" variables, u,v,w, etc., for\nwhich only history-propositional variables may (...) be substituted and\nthat correspond to maximally linearly ordered subsets of instants.\nThis second type is for tense logics in which time is not linear\nand where at any moment there may exist alternative future courses\nof events. Quantifiers are included in both types but only for clock-\nand history-propositional variables. However, these quantifiers are\ngiven an essentially substitutional interpretation. In addition,\nbesides each clock-propositional variable being true at exactly one\ninstant, the semantics requires that for each instant there be at\nleast one clock-propositional variable true at that instant, which\nin effect amounts to having each instant of the model "denoted" in\nthe formalism by some clock-propositional variable. Thus it is not\nsurprising that quantification over clock-propositional variables\nturns out to have a "well behaved first-order semantics" (p. 284).\n{One axiom relating history- with clock-propositions seems to need\nrevision: CKTauTbuAUabUba. Since the clock-propositional variables\nmight be true at the same instant the consequent should include an\nalternative, namely, LCab.} Besides the standard truth-functional\nand tense operators G,H,F,P, the author includes L for "it is\nalways the case that". The model-theoretic earlier-than relation\nordering instants and the semantic truth-at (an instant) relation\nare formalized by Uab and Taα (for a wff α) which\nare defined respectively as LCbPa (whenever the clock-proposition\nb is the case the clock-proposition a was the case) and LCaα\n(α is the case whenever the clock-proposition a is the case).\nBecause the future tense operators are definable in terms of U\nand T and the latter are definable in terms of L and P, the\ndual of H, the author notes that his completeness proofs can be\nrestricted to L and H as primitive and with the future tense\noperators used for other interpretations, especially Prior, A.'s\nindeterminist "it will be the case that", where time is not linear.\nThe author concludes with some rather technical observations showing\nthat "in ordinary tense logics the instants are nonstandard elements\nof the models. This provides", according to the author, "a semantic\npressure to build the instants into tense logic, so that they will\nappear as standard elements in the models" (p. 283). (shrink)