A new combined temporal logic called synchronized linear-time temporal logic (SLTL) is introduced as a Gentzen-type sequent calculus. SLTL can represent the n -Cartesian product of the set of natural numbers. The cut-elimination and completeness theorems for SLTL are proved. Moreover, a display sequent calculus δ SLTL is defined.

Hypersequent calculus, developed by A. Avron, is one of the most interesting proof systems suitable for nonclassical logics. Although HC has rather simple form, it increases significantly the expressive power of standard sequent calculi. In particular, HC proved to be very useful in the field of proof theory of various nonclassical logics. It may seem surprising that it was not applied to temporal logics so far. In what follows, we discuss different approaches to formalization of logics of linear frames (...) and provide a cut-free HC formalization ofKt4.3, the minimal temporal logic of linear frames, and some of its extensions. The novelty of our approach is that hypersequents are defined not as finite sets but as finite lists of ordinary sequents. Such a solution allows both linearity of time flow, and symmetry of past and future, to be incorporated by means of six temporal rules. Extensions of the basic calculus with simple structural rules cover logics of serial and dense frames. Completeness is proved by Schütte/Hintikka-style argument using models built from saturated hypersequents. (shrink)

We present an overview of linear-time temporal logics with Presburger constraints whose models are sequences of tuples of integers. Such formal specification languages are well-designed to specify and verify systems that can be modelled with counter systems. The paper recalls the general framework of LTL over concrete domains and presents the main decidability and complexity results related to fragments of Presburger LTL. Related formalisms are also briefly presented.

The papers collected in this volume, although dealing with several different themes, congeal around a debate about the ways and extent of the dominance of linear time and progressive history and the concomitant delineation of the nation in Chinese and Japanese historiography.

Most of the descriptions of interval time structures in the first order predicate calculus are based on linear time. However, in the case of intervals, abandoning the condition oflinearity (e.g.LIN in van Benthem's systems) is not sufficient. In this paper, some properties of non-linear time structures are discussed. The most important one is the characterization of location of intervals in a fork of branches. This is connected with the fact that an interval can contain non-collinear (...) subintervals. As a result of non-linearity, some basic properties of interval structures must be formulated in a weaker form. Moreover, time must be filled by intervals to indicate that time cannot pass without events occurring in it. Finally, it is shown that when intervals cannot contain non-collinear subintervals, most of the conditions described in the paper are satisfied. (shrink)

The art of Simon Finn has always had a markedly temporal dynamic. Vast structures built and annihilated again and again across different media, their fragmentation across space and time simultaneously methodical and darkly chaotic. Roiling waters and eldritch surfaces held captive in their unrest. Finn’s works render cycles of construction and disintegration, of stasis and motion, in ways that shed light upon the underlying structures of our experience of time while shattering simplistic notions of linearity. This is nowhere (...) more apparent than in Instability, through which Finn allows us to explore the intertwining of personal and historical time, ancestral memory and radical futurity, artefactual form and temporal function. (shrink)

It is known that linear-time temporal logic is a useful logic for verifying and specifying concurrent systems. In this paper, phase semantics for LTL and its substructural refinements is introduced, and the completeness and cut-elimination theorems for LTL and its refinements are proved based on this semantics.

We show that the bounded arithmetic theory V0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy . The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai.

The famous Allen's interval relations constraint propagation algorithm was intended for linear time. Its 13 primitive relations define all the possible mutual locations of two intervals on the time-axis. In this paper an application of the algorithm for non-linear time is suggested. First, a new primitive relation is added. It is called excludes since an occurrence of one event in a certain course of events excludes an occurrence of the other event in this course. Next, (...) new composition rules for relations between intervals are presented: some of the old rules are extended by the relation excludes, and entirely new ones are formulated for composing the relation excludes with the other relations. Four different composition tables are considered. The choice of a composition table depends on whether time is branching or not, and whether intervals can contain non-collinear subintervals or not. (shrink)

This study introduces refutation-aware Gentzen-style sequent calculi and Kripke-style semantics for propositional until-free linear-time temporal logic. The sequent calculi and semantics are constructed on the basis of the refutation-aware setting for Nelson’s paraconsistent logic. The cut-elimination and completeness theorems for the proposed sequent calculi and semantics are proven.

Temporal epistemic logics are known, from results of Halpern and Vardi, to have a wide range of complexities of the satisfiability problem: from PSPACE, through non-elementary, to highly undecidable. These complexities depend on the choice of some key parameters specifying, inter alia, possible interactions between time and knowledge, such as synchrony and agents' abilities for learning and recall. In this work we develop practically implementable tableau-based decision procedures for deciding satisfiability in single-agent synchronous temporal-epistemic logics with interactions between (...) class='Hi'>time and knowledge. We discuss some complications that occur, even in the single-agent case, when interactions between time and knowledge are assumed and show how the method of incremental tableaux can be adapted to work in EXPSPACE, respectively 2EXPTIME, for these logics, thereby also matching the upper bounds obtained for them by Halpern and Vardi. (shrink)

The present study traces and analyzes the ideas of linear time as depicted in some of the texts of the Ṛgveda, the Atharvaveda, the Kauṣītakibrāhmaṇa and the Mahābhārata, and as presented in the texts of early Buddhism. From the thread of fate, which is the path of man, narrative, identity, through the web woven by day and night or by the two goddesses of fate, through the web of sacrifice, to dependent origination in early Buddhism, all these images (...) and ideas are closely related with the notion of linear time. To go beyond this linear time, beyond the notion of LIFE IS A JOURNEY, is a penetration into the unspeakable, “into” the world beyond, “into” freedom. (shrink)

In a paper from the 1980s, Byrd claims that the logic of "eventual permanence" for linear time is KD5. In this note we take up Byrd's novel argument for this and, treating the problem as one concerning translational embeddings, show that rather than KD5 the correct logic of "eventual permanence" is KD45.

In this paper we present a theory for reasoning about actions which is based on Dynamic Linear Time Temporal Logic . DLTL is a simple extension of propositional temporal logic of linear time in which regular programs of propositional dynamic logic can be used for indexing temporal modalities. The action theory we define allows to reason with incomplete initial states, to do postdiction and to deal with ramifications and with nondeterministic actions, which are captured by possibly (...) alternative extensions . The expressiveness of temporal logic is exploited to enhance the action language by allowing the definition of general temporal constraints as well as complex actions in the specification of the domain description. We show that the temporal projection problem and the planning problem can be modelled as satisfiability problems in DLTL. (shrink)

In recent years large amounts of electronic texts have become available. While the first of these corpora had only a low level of annotation, the more recent ones are annotated with refined syntactic information. To make these rich annotations accessible for linguists, the development of query systems has become an important goal. One of the main difficulties in this task consists in the choice of the right query language, a language which at the same time should be powerful enough (...) to let users formulate the queries they want and which should be efficiently evaluable to keep query response times short. There is a widespread belief that such a query language does not exist. It is therefore the aim of this paper to show that there is indeed a powerful query language that can be efficiently evaluated. We propose the use of monadic second-order logic as a query language. We show that a query in this language can be evaluated in linear time in the size of a tree in the corpus. We also provide examples of complicated linguistic queries expressed in monadic second-order logic thereby demonstrating the high expressive power of the language. (shrink)

ABSTRACT The question of axiomatizability of first-order temporal logics is studied w.r.t. different semantics and several restrictions on the language. The validity problem for logics admitting flexible interpretations of the predicate symbols or allowing at least binary predicate symbols is shown to be ?1 1-complete. In contrast, it is decidable for temporal logics with rigid monadic predicate symbols but without function symbols and identity.

This paper presents decomposition of the fourth-order Euler-type linear time-varying system as a commutative pair of two second-order Euler-type systems. All necessary and sufficient conditions for the decomposition are deployed to investigate the commutativity, sensitivity, and the effect of disturbance on the fourth-order LTVS. Some systems are commutative, and some are not commutative, while some are commutative under certain conditions. Based on this fact, the commutativity of fourth-order Euler-type LTVS is investigated by introducing the commutative requirements, theories, and (...) conditions. The fourth-order Euler-type LTVSs are investigated into commutative pairs of twice Euler-type second-order linear time-varying systems. The decomposition theories and conditions are derived, proved, and solved to simplify the use of commutativity for practical and industrial uses. Some fourth-order systems are sensitive toward change in initial conditions or parameters while others are not, and the effect due to disturbance also varies within systems. Furthermore, the stability and robustness of systems have so many issues. But we consider fourth-order Euler-type LTVS to observe, investigate, and tackle these issues. Lastly, the realization of fourth-order LTVS from cascaded two second-order systems can be laboratory experimented which is an open problem for future engineers to investigate. However, the theoretical results show a good agreement with the simulation results is considered in this work. Perhaps it might have unlimited physical applications in science and engineering as well as theoretical contribution. But beyond any reasonable doubt, the novelty is guaranteed because this study is the first of its kind that introduces the decomposition of the fourth-order Euler-type linear time-varying system as a commutative pair of two second-order Euler-type systems. Illustrative examples are presented to support the results. (shrink)

This is a sequel article to [10] where a hypersequent calculus for some temporal logics of linear frames includingKt4.3and its extensions for dense and serial flow of time was investigated in detail. A distinctive feature of this approach is that hypersequents are noncommutative, i.e., they are finite lists of sequents in contrast to other hypersequent approaches using sets or multisets. Such a system in [10] was proved to be cut-free HC formalization of respective logics by means of semantical (...) argument. In this article we present an equivalent variant of this calculus for which a constructive syntactical proof of cut elimination is provided. (shrink)

We present an axiomatisation for the first-order temporal logic with connectives Until and Since over the class of all linear flows of time. Completeness of the axiom system is proved.We also add a few axioms to find a sound and complete axiomatisation for the first order temporal logic of Until and Since over rational numbers time.

This article examines how non-linear time and circularity are deployed in the historical novel Nehanda, written by Zimbabwean author Yvonne Vera. Using Adriana Cavarero’s work on inclination...

We prove that all finitely axiomatizable tense logics with temporal operators for ‘always in the future’ and ‘always in the past’ and determined by linear fows time are coNP-complete. It follows, for example, that all tense logics containing a density axiom of the form ■n+1F p → nF p, for some n ≥ 0, are coNP-complete. Additionally, we prove coNP-completeness of all ∩-irreducible tense logics. As these classes of tense logics contain many Kripke incomplete bimodal logics, we obtain (...) many natural examples of Kripke incomplete normal bimodal logics which are nevertheless coNP-complete. (shrink)

The paper aims at providing the multi-modal propositional logic LTK with a sound and complete axiomatisation. This logic combines temporal and epistemic operators and focuses on m odeling the behaviour of a set of agents operating in a system on the background of a temporal framework. Time is represented as linear and discrete, whereas knowledge is modeled as an S5-like modality. A further modal operator intended to represent environment knowledge is added to the system in order to achieve (...) the expressive power sufficient to describe the piece of information available to the agents at each moment in the flow of time. (shrink)

This paper investigates logical aspects of combining linear orders as semantics for modal and temporal logics, with modalities for possible paths, resulting in a variety of branching time logics over classes of trees. Here we adopt a unified approach to the Priorean, Peircean and Ockhamist semantics for branching time logics, by considering them all as fragments of the latter, obtained as combinations, in various degrees, of languages and semantics for linear time with a modality for (...) possible paths. We then consider a hierarchy of natural classes of trees and bundled trees arising from a given class of linear orders and show that in general they provide different semantics. We also discuss transfer of definability from linear orders to trees and introduce a uniform translation from Priorean to Peircean formulae which transfers definability of properties of linear orders to definability of properties of all paths in trees. (shrink)

The paper studies the logic TL(NBox+-wC) – logic of discrete linear time with current time point clusters. Its language uses modalities Diamond+ (possible in future) and Diamond- (possible in past) and special temporal operations, – Box+w (weakly necessary in future) and Box-w (weakly necessary in past). We proceed by developing an algorithm recognizing theorems of TL(NBox+-wC), so we prove that TL(NBox+-wC) is decidable. The algorithm is based on reduction of formulas to inference rules and converting the rules (...) in special reduced normal form, and, then, on checking validity of such rules in models of singleexponential size in the rules. Also we consider the admissibility problem for TL(NBox+-wC) and show how to reduce the problem for admissibility to the decidability of TL(NBox+-wC) itself using definable universal modalities. (shrink)

Temporal justification logic is a new family of temporal logics of knowledge in which the knowledge of agents is modelled using a justification logic. In this paper, we present various temporal justification logics involving both past and future time modalities. We combine Artemov’s logic of proofs with linear temporal logic with past, and we also investigate several principles describing the interaction of justification and time. We present two kinds of semantics for our temporal justification logics, one based (...) on interpreted systems and Fitting models and the other based on Mkrtychev models, and further, we establish soundness and completeness. We show that the internalization property holds in some of the temporal justification logics. We further investigate the two well-known epistemic-temporal notions of no forgetting and no learning in the framework of justification logics. Finally, we present temporal justification logics that avoid the logical omniscience problem. (shrink)

Temporal logic can be used to describe processes: their behaviour ischaracterized by a set of temporal models axiomatized by a temporaltheory. Two types of models are most often used for this purpose: linearand branching time models. In this paper a third approach, based onsocalled joint closure models, is studied using models which incorporateall possible behaviour in one model. Relations between this approach andthe other two are studied. In order to define constructions needed torelate branching time models, appropriate algebraic (...) notions are defined(in a category theoretical manner) and exploited. In particular, thenotion of joint closure is used to construct one model subsuming a setof models. Using this universal algebraic construction we show that aset of linear models can be merged to a unique branching time model.Logical properties of the described algebraic constructions are studied.The proposed approach has been successfully aplied to obtain anappropriate semantics for non-monotonic reasoning processes based ondefault logic. References are discussed that show the details of theseapplications. (shrink)

Aggregation of variables allows to approximate a large scale dynamical system (the micro-system) involving many variables into a reduced system (the macro-system) described by a few number of global variables. Approximate aggregation can be performed when different time scales are involved in the dynamics of the micro-system. Perturbation methods enable to approximate the large micro-system by a macro-system going on at a slow time scale. Aggregation has been performed for systems of ordinary differential equations in which time (...) is a continuous variable. In this contribution, we extend aggregation methods to time-discrete models of population dynamics. Time discrete micro-models with two time scales are presented. We use perturbation methods to obtain a slow macro-model. The asymptotic behaviours of the micro and macro-systems are characterized by the main eigenvalues and the associated eigenvectors. We compare the asymptotic behaviours of both systems which are shown to be similar to a certain order. (shrink)