Unification in linear temporal logic LTL

We prove that a propositional Linear Temporal Logic with Until and Next (LTL) has unitary unification. Moreover, for every unifiable in LTL formula A there is a most general projective unifier, corresponding to some projective formula B, such that A is derivable from B in LTL. On the other hand, it can be shown that not every open and unifiable in LTL formula is projective. We also present an algorithm for constructing a most general unifier.     

Proof-theoretical investigation of temporal logic with time gaps

In the paper, the first-order intuitionistic temporal logic sequent calculus LBJ is considered. The invertibility of some of the LBJ rules, syntactic admissibility of the structural rules and the cut rule in LBJ, as well as Harrop and Craig's interpolation theorems for LBJ are proved. Gentzen's midsequent theorem is proved for the LBJ' calculus which is obtained from LBJ by removing the antecedent disjunction rule from it. Published in Lietuvos Matematikos Rinkinys, Vol. 40, No. 3, pp. 255–276, July–September, 2000.     

A note on unbounded metric temporal logic over dense time domains

We investigate the consequences of removing the infinitary axiom and rules from a previously defined proof system for a fragment of propositional metric temporal logic over dense time (see [1]). (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Infinitary calculus for a restricted first-order linear temporal logic without contraction on quantified formulas

An infinitary calculus for a restricted fragment of the first-order linear temporal logic is considered. We prove that for this fragment one can construct the infinitary calculusG _Lω ^* without contraction on predicate formulas. The calculusG _Lω ^* possesses the following properties: (1) the succedent rule for the existential quantifier is included into the corresponding axiom; (2) the premise of the antecedent rule for the universal quantifier does not contain a duplicate of the main formula. The soundness and completness ofG _Lω ^* are also proved. Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 39, No. 3, pp. 378–397, July–September, 1999. Translated by R. Lapinskas     

An axiomatization for the linear logic of knowledge and time LTK r with intransitive time relation

We study the problem of the axiomatization of the linear multimodal logic of knowledge and time LTK _r with reflexive intransitive time relation. The logic is defined semantically as the set of formulas true on frames of a special kind. The LTK _r -frames are linear chains of clusters connected by a reflexive intransitive relation R _T which simulates time. Elements inside a cluster are connected by several equivalence relations imitating the knowledge of different agents. The main result of the article is the proof of the fact that the finite set of formulas proposed by the authors is an axiomatization of the logic LTK _r with reflexive intransitive time relation.     

Models of linear logic

We engage a study of nonmodal linear logic which takes times ⊗ and the linear conditional ⊸ to be the basic connectives instead of times and linear negation ()^⊥ as in Girard's approach. This difference enables us to obtain a very large subsystem of linear logic (called positive linear logic) without an involutionary negation (if the law of double negation is removed from linear logic in Girard's formulation, the resulting subsystem is extremely limited). Our approach enables us to obtain several natural models for various subsystems of linear logic, including a generic model for the so-called minimal linear logic. In particular, it is seen that these models arise spontaneously in the transition from set theory to multiset theory. We also construct a model of full (nonmodal) linear logic that is generic relative to any model of positive linear logic. However, the problem of constructing a generic model for positive linear logic remains open. Bibliography: 2 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 23–35. Original     

A two-dimensional metric temporal logic

We introduce a two-dimensional metric (interval) temporal logic whose internal and external time flows are dense linear orderings. We provide a suitable semantics and a sequent calculus with axioms for equality and extralogical axioms. Then we prove completeness and a semantic partial cut elimination theorem down to formulas of a certain type.     

Saturated calculus for Horn-like sequents of a complete class of a linear temporal first order logic

A saturated calculus for the so-called Horn-like sequents of a complete class of a linear temporal logic of the first order is described. The saturated calculus contains neither induction-like postulates nor cut-like rules. Instead of induction-like postulates the saturated calculus contains a finite set of “saturated” sequents, which (1) capture and reflect the periodic structure of inductive reasoning (i.e., a reasoning which applies induction-like postulates); (2) show that “almost nothing new” can be obtained by continuing the process of derivation of a given sequent; (3) present an explicit way of generating the so-called invariant formula in induction-like rules. The saturated calculus for Horn-like sequents allows one: (1) to prove in an obvious way the completeness of a restricted linear temporal logic of the first order; (2) to construct a computer-aided proof system for this logic; (3) to prove the decidability of this logic for logically decidable Horn-like sequents. Bibliography: 15 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 123–144. Translated by R. Pliuškevičius.     

Local computation in linear logic

This work deals with the exponential fragment of Girard's linear logic ([3]) without the contraction rule, a logical system which has a natural relation with the direct logic ([10], [7]). A new sequent calculus for this logic is presented in order to remove the weakening rule and recover its behavior via a special treatment of the propositional constants, so that the process of cut-elimination can be performed using only “local” reductions. Hence a typed calculus, which admits only local rewriting rules, can be introduced in a natural manner. Its main properties — normalizability and confluence — has been investigated; moreover this calculus has been proved to satisfy a Curry-Howard isomorphism ([6]) with respect to the logical system in question. MSC: 03B40, 03F05.     

Maximality of linear continuous logic

The linear compactness theorem is a variant of the compactness theorem holding for linear formulas. We show that the linear fragment of continuous logic is maximal with respect to the linear compactness theorem and the linear elementary chain property. We also characterize linear formulas as those preserved by the ultramean construction.     

On temporal logic S4Dbr

In this paper, we study the temporal logic S4Dbr with two temporal operators “always” and “eventually.” An equivalent sequent calculus is presented with formulae as modal clauses or modal clauses starting with operator “always.” An upper bound of deduction tree is given for propositional logic. A theorem prover for propositional logic is written in SWI-Prolog. Published in LietuvosMatematikos Rinkinys, Vol. 46, No. 2, pp. 203–214, April–June, 2006.     

Preservation theorems in linear continuous logic

Linear continuous logic is the fragment of continuous logic obtained by restricting connectives to addition and scalar multiplications. Most results in the full continuous logic have a counterpart in this fragment. In particular a linear form of the compactness theorem holds. We prove this variant and use it to deduce some basic preservation theorems.     

Modeling linear logic with implicit functions

Just as intuitionistic proofs can be modeled by functions, linear logic proofs, being symmetric in the inputs and outputs, can be modeled by relations (for example, cliques in coherence spaces). However generic relations do not establish any functional dependence between the arguments, and therefore it is questionable whether they can be thought as reasonable generalizations of functions. On the other hand, in some situations (typically in differential calculus) one can speak in some precise sense about an implicit functional dependence defined by a relation. It turns out that it is possible to model linear logic with implicit functions rather than general relations, an adequate language for such a semantics being (elementary) differential calculus. This results in a non-degenerate model enjoying quite strong completeness properties.     

Non decomposable connectives of linear logic

This paper studies the so-called generalized multiplicative connectives of linear logic, focusing on the question of finding the “non-decomposable” ones, i.e., those that cannot be expressed as combinations of the default binary connectives of multiplicative linear logic, ⊗ (times) and ⅋ (par). In particular, we concentrate on generalized connectives of a surprisingly simple form, called “entangled connectives”, and prove a characterization theorem giving a criterion for identifying the undecomposable entangled ones.     

Time-constrained temporal logic control of multi-affine systems

In this paper, we consider the problem of controlling a dynamical system such that its trajectories satisfy a temporal logic property in a given amount of time. We focus on multi-affine systems and specifications given as syntactically co-safe linear temporal logic formulas over rectangular regions in the state space. The proposed algorithm is based on estimating the time bounds for facet reachability problems and solving a time optimal reachability problem on the product between a weighted transition system and an automaton that enforces the satisfaction of the specification. A random optimization algorithm is used to iteratively improve the solution.     

The complexity of temporal logic over the reals

It is shown that the decision problem for the temporal logic with until and since connectives over real-numbers time is PSPACE-complete. This is the most practically useful dense time temporal logic.     

Bounded linear-time temporal logic: A proof-theoretic investigation

Propositional and first-order bounded linear-time temporal logics (BLTL and FBLTL, respectively) are introduced by restricting Gentzen type sequent calculi for linear-time temporal logics. The corresponding Robinson type resolution calculi, RC and FRC for BLTL and FBLTL respectively are obtained. To prove the equivalence between FRC and FBLTL, a temporal version of Herbrand theorem is used. The completeness theorems for BLTL and FBLTL are proved for simple semantics with both a bounded time domain and some bounded valuation conditions on temporal operators. The cut-elimination theorems for BLTL and FBLTL are also proved using some theorems for embedding BLTL and FBLTL into propositional (first-order, respectively) classical logic. Although FBLTL is undecidable, its monadic fragment is shown to be decidable.