CT image reconstruction is a challenging inverse problem of estimating image intensities from sensor signals. While deep learning-based methods hold promise, they are typically classified into fully-supervised, self-supervised, and case-by-case approaches, each offering distinct advantages and limitations. Among these, case-by-case reconstruction techniques, exemplified by models like NeRP, provide the advantage of flexible data-sampling and image sizes, making them well-suited for the complex CT inverse problem. However, existing case-by-case models encounter difficulties in achieving precise reconstructions, particularly in sparse-view scenarios. To address this limitation, we propose tomo-NeRL, a novel implicit reconstruction model that incorporates tomographic information of individual pixels within the reconstruction network. By harnessing this tomo-graphic data for implicit inverse learning, tomo-NeRL enhances reconstruction quality while effectively mitigating artifacts. The core innovation of tomo-NeRL lies in defining and extracting tomographic insights, such as visual characteristics and spatial variations specific to tomographic imaging, from the sinogram data for individual pixels. Moreover, our work introduces an adaptive inversion framework that amalgamates tomographic information from diverse projection angles, constructing a latent feature space that enhances the reconstruction process. Extensive experiments unequivocally showcase tomo-NeRL’s outstanding reconstruction performance, excelling in artifact suppression and detail preservation, especially in sparse-view scenarios.

With the advent of location-based social networks, users can tag their daily activities in different locations through check-ins. These check-in locations signify user preferences for various socio-spatial activities and can be used to improve the quality of services in some applications such as recommendation systems, advertising, and group formation. To support such applications, in this paper, we formulate a new problem of identifying top-k Socio-Spatial co-engaged Location Selection (SSLS) for users in a social graph, that selects the best set of k locations from a large number of location candidates relating to the user and her friends. The selected locations should be (i) spatially and socially relevant to the user and her friends, and (ii) diversified both spatially and socially to maximize the coverage of friends in the socio-spatial space. To address the NP-hard and challenging problem, we first develop an exact solution by designing some pruning strategies, and also develop an approximate solution by deriving relaxed bounds and advanced termination rules. To accelerate the efficiency, we further develop a fast exact approach and a meta-heuristic approximate approach. Finally, extensive experiments are conducted to evaluate the performance of our proposed algorithms against three adapted existing methods using four real-world datasets.

In this study we propose obstacle-aware evolution-ary algorithms to identify optimised network topologies for electricity distribution networks including isolated microgrids or stand-alone power systems. We outline the extension of two evo-lutionary algorithms that are modified to consider different types of geographically constrained areas in electricity distribution planning. These areas are represented as polygonal obstacles that either cannot be traversed or cause a higher weight factor when traversing. Both proposed evolutionary algorithms are extended such that they find optimised network solutions that avoid solid obstacles and consider the increased cost of traversing soft obstacles. The algorithms are tested and compared on different types of problem instances with solid and soft obstacles and the problem-specific evolutionary algorithm can be shown to successfully find low cost network topologies on a range of different test instances.

In this paper we address the Euclidean Steiner tree problem in the plane in the presence of soft and solid polygonal obstacles. The Euclidean Steiner tree problem is a well-known NP-hard problem with different applications in network design. Given a set of terminal nodes in the plane the aim is to find a shortest-length interconnection of the terminals allowing further nodes, so-called Steiner points, to be added. In many real-life scenarios there are further constraints that need to be considered. Regions in the plane that cannot be traversed or can only be traversed at a higher cost can be approximated by polygonal areas that either need to be avoided (solid obstacles) or come with a higher cost of traversing (soft obstacles). We propose a genetic algorithm that uses problem-specific representation and operators to solve this problem and show that the algorithm can solve various test scenarios of different sizes. The presented approach appears to outperform current heuristic approaches for the Steiner tree problem with soft obstacles and was evaluated on larger test instances as well.

Cameras have been widely used in traffic operations. While many technologically smart camera solutions in the market can be integrated into Intelligent Transport Systems (ITS) for automated detection, monitoring and data generation, many Network Operations (a.k.a Traffic Control) Centres still use legacy camera systems as manual surveillance devices. In this paper, we demonstrate effective use of these older assets by applying computer vision techniques to extract traffic data from videos captured by legacy cameras. In our proposed vision-based pipeline, we adopt recent state-of-the-art object detectors and transfer-learning to detect vehicles, pedestrians, and cyclists from monocular videos. By weakly calibrating the camera, we demonstrate a novel application of the image-to-world homography which gives our monocular vision system the efficacy of counting vehicles by lane and estimating vehicle length and speed in real-world units. Our pipeline also includes a module which combines a convolutional neural network (CNN) classifier with projective geometry information to classify vehicles. We have tested it on videos captured at several sites with different traffic flow conditions and compared the results with the data collected by piezoelectric sensors. Our experimental results show that the proposed pipeline can process 60 frames per second for pre-recorded videos and yield high-quality metadata for further traffic analysis.

Pedestrian path prediction is a very challenging problem because scenes are often crowded or contain obstacles. Existing state-of-the-art long short-term memory (LSTM)-based prediction methods have been mainly focused on analyzing the influence of other people in the neighborhood of each pedestrian while neglecting the role of potential destinations in determining a walking path. In this article, we propose classifying pedestrian trajectories into a number of route classes (RCs) and using them to describe the pedestrian movement patterns. Based on the RCs obtained from trajectory clustering, our algorithm, which we name the prediction of pedestrian paths by LSTM (PoPPL), predicts the destination regions through a bidirectional LSTM classification network in the first stage and then generates trajectories corresponding to the predicted destination regions through one of the three proposed LSTM-based architectures in the second stage. Our algorithm also outputs probabilities of multiple predicted trajectories that head toward the destination regions. We have evaluated PoPPL against other state-of-the-art methods on two public data sets. The results show that our algorithm outperforms other methods and incorporating potential destination prediction improves the trajectory prediction accuracy.

This article provides an extensive review of algorithms for constructing Minkowski sums and differences of polygons and polyhedra, both convex and non-convex, commonly known as no-fit polygons and configuration space obstacles. The Minkowski difference is a set operation, which when applied to shapes defines a method for efficient overlap detection, providing an important tool in packing and motion-planning problems. This is the first complete review on this specific topic, and aims to unify algorithms spread over the literature of separate disciplines.

Single object visual tracking is a fundamental problem in computer vision and has many applications. Given only the location of the target of interest in the first video frame, a visual tracking algorithm must track the target until the end of the video while having to face challenging factors such as illumination change and scale variation. In this paper, we formulate this tracking problem in a framework of maximum entropy reinforcement learning where the agent is our visual tracker and the goal is to learn a tracking policy that maximises both the expected reward and its entropy so as to achieve a balance between exploitation and exploration. The aim of our tracking framework is to improve the tracking accuracy while giving the tracking agent the ability to avoid getting stuck on a nontarget object. Extensive experiments have been performed on a range of benchmarks where our method achieves state-of-the-art performance. Furthermore, we demonstrate that, in contrast to other visual trackers based on deep reinforcement learning, our method can run in real-time while maintaining high tracking accuracy.

Visual tracking has been an active research area in computer vision for decades. However, the performance of existing techniques is still challenged by various factors, such as occlusion and change in appearance of the target. In this paper, we propose a novel framework based on correlation filtering and probabilistic finite state machines (FSMs) to handle occlusion. In our tracking framework, the target is partitioned into several parts whose occlusion states are automatically detected. A set of states for the target is defined in terms of the combination of the parts' occlusion states. The probabilistic FSMs are then used to model the target's state transitions so as to reduce the effect of noise in the output response maps of correlation filters. Our target model's update strategy is adaptable online depending on the estimated state of the target. Extensive experiments have been performed on several public benchmarks and the proposed algorithm achieves competitive results against state-of-the-art techniques.

One of the factors hindering the use of classification models in decision making is that their predictions may contradict expectations. In domains such as finance and medicine, the ability to include knowledge of monotone (nondecreasing) relationships is sought after to increase accuracy and user satisfaction. As one of the most successful classifiers, attempts have been made to do so for Random Forest. Ideally a solution would (a) maximise accuracy; (b) have low complexity and scale well; (c) guarantee global monotonicity; and (d) cater for multi-class. This paper first reviews the state-of-theart from both the literature and statistical libraries, and identifies opportunities for improvement. A new rule-based method is then proposed, with a maximal accuracy variant and a faster approximate variant. Simulated and real datasets are then used to perform the most comprehensive ordinal classification benchmarking in the monotone forest literature. The proposed approaches are shown to reduce the bias induced by monotonisation and thereby improve accuracy.

The clustering of networks in order to optimise one or more given objectives is a highly researched field with many real-world applications. One of these applications is the clustering of a current or potential future electricity network in order to identify an optimised network topology that could consist of microgrids and stand-alone power systems. This research paper gives a brief overview of the current applications of network partitioning and the different methodologies found in the literature. Then, a novel evolutionary algorithm approach is presented which optimises the topology of rural electricity distribution networks considering a problem-specific objective cost function. Given a set of electricity customer loads and locations, the aim is to identify optimal microgrid and standalone power system formations to minimise the total network costs over a certain time period. The latter part entails a brief introduction to microgrids and some theoretical background, a description of the evaluated cost function, and an outline of the problem-specific evolutionary algorithm used for optimising the network.

In recent years, spatial keyword query has attracted wide-spread research attention due to the popularity of the location-based services. To efficiently support the online spatial keyword query processing, the data owners need to outsource their data and the query processing service to cloud platforms. However, the outsourcing services may raise privacy leaking issues because the cloud server on the platforms may not be trusted for both data owners and query users. Therefore, in this work, we first propose and formalize the problem of privacy-preserving boolean spatial keyword query under the widely accepted Known Background Thread Model. And then, we devise a novel privacy-preserving spatial-textual Bloom Filter encoding structure and an encrypted R-tree index. They can maintain both spatial and text information together in a secure way while answering the encrypted spatial keyword queries without the need for data decryption. To further accelerate the query processing, a compressed encrypted index is provided to deal with the challenges of the large dimension expansion and the expensive space consumption in the encrypted R-tree index. In addition, we develop the corresponding algorithms based on the designed index, and present the in-depth security analysis to show our work's satisfaction meeting the strong secure scheme. Finally, we demonstrate the performance of our proposed index and algorithms by conducting extensive experiments on four datasets under various system settings.

Vehicle re-identification (Re-ID) plays a key role in many smart traffic management systems. Re-identifying a vehicle can be very challenging because the differences in visual appearances between pairs of vehicles are sometimes extremely subtle if they have the same colour and the same model. Given an image of a vehicle, most existing techniques adopt a global feature representation where details may be ignored. In this paper, we propose an Self-Attention Stair Feature Fusion model to learn the discriminative features for vehicle Re-ID. The model is designed to extract multi-level features in order to capture as much small details as possible. We also propose a Temporal Bayesian Re-Ranking method to exploit the spatial-temporal information in the vehicles' travel patterns. Our algorithm has been tested against state-of-the-art techniques on popular benchmarks. The results show that our algorithm outperforms other state-of-the-art techniques by a large margin.

Linear temporal logic (LTL) is commonly used in model checking tasks; moreover, it is well-suited for the formalization of technical requirements. However, the correct specification and interpretation of temporal logic formulas require a strong mathematical background and can hardly be done by domain experts, who, instead, tend to rely on a natural language description of the intended system behaviour. In such situations, a system that is able to automatically translate English sentences into LTL formulas, and vice versa, would be of great help. While the task of rendering an LTL formula into a more readable English sentence may be carried out in a relatively easy way by properly parsing the formula, the converse is still an open problem, due to the inherent difficulty of interpreting free, natural language texts. Although several partial solutions have been proposed in the past, the literature still lacks a critical assessment of the work done. We address such a shortcoming, presenting the current state of the art for what concerns the English-to-LTL translation problem, and outlining some possible research directions.

The prediction of the surrounding pedestrians' walking paths is a vital part for autonomous driving systems in the aspect of traffic safety. In this paper, we propose a pipeline which tracks pedestrians captured by a stereo camera system onboard a mobile vehicle, composes the pedestrian tracklets, clusters the tracklets to form trajectories, and matches the trajectories. The output 3D pedestrian trajectories can be used for further applications such as pedestrian trajectory prediction for driverless vehicles. Our algorithm has been compared with various state-of-art pedestrian tracking methods. Our experimental results show that the visual temporal features computed by our algorithm are effective for trajectory representation and that, by incorporating tracklet clustering into the pipeline, the pedestrian tracking performance is improved.

Pedestrian path forecasting is crucial in applications such as smart video surveillance. It is a challenging task because of the complex crowd movement patterns in the scenes. Most of existing state-of-the-art LSTM based prediction methods require rich context like labelled static obstacles, labelled entrance/exit regions and even the background scene. Furthermore, incorporating contextual information into trajectory prediction increases the computational overhead and decreases the generalization of the prediction models across different scenes. In this paper, we propose a joint Location-Velocity Attention LSTM based method to predict trajectories. Specifically, a module is designed to tweak the LSTM network and an attention mechanism is trained to learn to optimally combine the location and the velocity information of pedestrians in the prediction process. We have evaluated our approach against other baselines and state-of-the-art methods on several publicly available datasets. The results show that it not only outperforms other prediction methods but it also has a good generalization ability.

This paper presents a novel framework for decentralized monitoring of Linear Temporal Logic (LTL) formulas, under the situation where processes are synchronous and the formula is represented as a tableau. The tableau technique allows one to construct a semantic tree for the input LTL formula, which can be used to optimize the decentralized monitoring of LTL in various ways. Given a system P and an LTL formula φ, we construct a tableau T φ . The tableau T φ is used for two purposes: (a) to synthesize an efficient round-robin communication policy for processes, and (b) to find the minimal ways to decompose the formula and communicate observations of processes in an efficient way. In our framework, processes can propagate truth values of both atomic and compound formulas (non-atomic formulas) depending on the syntactic structure of the input LTL formula and the observation power of processes. We demonstrate that this approach of decentralized monitoring based on tableau construction is more straightforward, more flexible, and more likely to yield efficient solutions than alternative approaches.

In many machine learning applications there exists prior knowledge that the response variable should be non-decreasing in one or more of the features. For example, the chance of a tumour being malignant should not decrease with increasing diameter (all else being equal). While a number of classification algorithms make use of monotone knowledge, many are limited to full monotonicity (in all features). Taking inspiration from instance based classifiers, we present a framework for monotone additive rule ensembles that is the first to cater for partial monotonicity (in some features). We demonstrate it by developing a partially monotone instance based classifier based on L1 cones. Experiments show that the algorithm produces reasonable results on real data sets while ensuring perfect partial monotonicity.

In timeline-based planning, domains are described as sets of independent, but interacting, components, whose behaviour over time (the set of timelines) is governed by a set of temporal constraints. A distinguishing feature of timeline-based planning systems is the ability to integrate planning with execution by synthesising control strategies for flexible plans. However, flexible plans can only represent temporal uncertainty, while more complex forms of nondeterminism are needed to deal with a wider range of realistic problems. In this paper, we propose a novel game-theoretic approach to timeline-based planning problems, generalising the state of the art while uniformly handling temporal uncertainty and nondeterminism. We define a general concept of timeline-based game and we show that the notion of winning strategy for these games is strictly more general than that of control strategy for dynamically controllable flexible plans. Moreover, we show that the problem of establishing the existence of such winning strategies is decidable using a doubly exponential amount of space.

Timed automata are powerful models for the analysis of real time systems. The optimal infinite scheduling problem for double-priced timed automata is concerned with finding infinite runs of a system whose long term cost to reward ratio is minimal. Due to the state-space explosion occurring when discretising a timed automaton, exact computation of the optimal infinite ratio is infeasible. This paper describes the implementation and evaluation of ant colony optimisation for approximating the optimal schedule for a given double-priced timed automaton. The application of ant colony optimisation to the corner-point abstraction of the automaton proved generally less effective than a random method. The best found optimisation method was obtained by formulating the choice of time delays in a cycle of the automaton as a linear program and utilizing ant colony optimisation in order to determine a sequence of profitable discrete transitions comprising an infinite behaviour.

Pedestrian trajectory prediction is an extremely challenging problem because of the crowdedness and clutter of the scenes. Previous deep learning LSTM-based approaches focus on the neighbourhood influence of pedestrians but ignore the scene layouts in pedestrian trajectory prediction. In this paper, a novel hierarchical LSTM-based network is proposed to consider both the influence of social neighbourhood and scene layouts. Our SS-LSTM, which stands for Social-Scene-LSTM, uses three different LSTMs to capture person, social and scene scale information. We also use a circular shape neighbourhood setting instead of the traditional rectangular shape neighbourhood in the social scale. We evaluate our proposed method against two baseline methods and a state-of-art technique on three public datasets. The results show that our method outperforms other methods and that using circular shape neighbourhood improves the prediction accuracy.

Abstract We consider Minkowski spacetime, the set of all point-events of spacetime under the relation of causal accessibility. That is, x can access y if an electromagnetic or (slower than light) mechanical signal could be sent from x to y. We use Prior’s tense language of F and P representing causal accessibility and its converse relation. We consider two versions, one where the accessibility relation is reflexive and one where it is irreflexive. In either case it has been an open problem, for decades, whether the logic is decidable or axiomatisable. We make a small step forward by proving, in each case, that the set of valid formulas over two-dimensional Minkowski spacetime is decidable and that the complexity of each problem is PSPACE-complete. A consequence is that the temporal logic of intervals with real endpoints under either the containment relation or the strict containment relation is PSPACE-complete, the same is true if the interval accessibility relation is “each endpoint is not earlier”, or its irreflexive restriction. We provide a temporal formula that distinguishes between three-dimensional and two-dimensional Minkowski spacetime and another temporal formula that distinguishes the two-dimensional case where the underlying field is the real numbers from the case where instead we use the rational numbers.

Linear Temporal Logic (LTL) is a de-facto standard formalism for expressing properties of systems and temporal constraints in formal verification, artificial intelligence, and other areas of computer science. The problem of LTL satisfiability is thus prominently important to check the consistency of these temporal specifications. Although adding past operators to LTL does not increase its expressive power, recently the interest for explicitly handling the past in temporal logics has increased because of the clarity and succinctness that those operators provide. In this work, a recently proposed one-pass tree-shaped tableau system for LTL is extended to support past operators. The modularity of the required changes provides evidence for the claimed ease of extensibility of this tableau system.

It has been shown that every temporal logic formula satisfiable over general linear time has a model than can be expressed as a finite Model Expression (ME). The reals are a subclass of general linear time, so similar techniques can be used for the reals. Although MEs are expressive enough for this task, they represent only a single class of elementary equivalent models. In the case where time is represented by integers, regular expressions are equivalent to automata. An ME is more similar to a single run of an automaton than the automaton itself. In linear time it is often useful to model a system as an automaton (or regular expression) rather than a single run of the automaton. In this paper we extend MEs with the operators from Regular Expressions to produce Regular Model Expressions (RegMEs). It is known that model checking temporal logic formulas over MEs is PSPACE-complete. We show that model checking temporal logic formulas over RegMEs is also PSPACE-complete.

RoCTL* was proposed to model and specify the robustness of reactive systems. RoCTL* extended CTL* with the addition of Obligatory and Robustly operators, which quantify over failure-free paths and paths with one more failure, respectively. This article gives an axiomatization for all the operators of RoCTL* with the exception of the Until operator; this fragment is able to express similar contrary-to-duty obligations to the full RoCTL* logic. We call this formal system NORA, and give a completeness proof. We also consider the fragments of the language containing only path quantifiers but where atoms are dependent on histories. We examine semantic properties and potential axiomatizations for these fragments.

Abstract The paper presents a new efficient algorithm for computing worst case execution time (WCET) of systems modelled as timed automata (TA). The algorithm uses a set of abstraction techniques that improve significantly the efficiency of WCET analysis of TA models with cyclic behaviour. We show that the proposed abstractions are exact with respect to the WCET problem in the sense that the WCET computed in the abstract model is equal to the one computed in the concrete model. We also compare our algorithm with the one implemented in the model checker UPPAAL which shows that when infinite cycles exist (i.e. cycles that can be run infinitely often), UPPAAL’s algorithm may not terminate, and when largely repetitive finite cycles exist (i.e. cycles that can be run a large number of times but finite), UPPAAL’s algorithm suffers from the state space explosion, thus leading to a low efficiency or resource exhaustion.

A number of procedures for checking the satisfiability of formulas in the important branching time temporal logic CTL* have recently been proposed. This paper instead focuses on automatic generation and verification of rewrite rules for computation tree logics; shows that non-local computation tree logics can be used to verify rewrite rules, including for CTL*; presents an efficient tableau for the non-local bundled variant NL-BCTL*; and shows that NL-BCTL* is 2EXPTIME-complete. We show that such rules can quickly simplify CTL* formulas. These simplified formulas are shorter and easier to reason with using existing decision procedures for CTL*, as demonstrated by significant speed-ups across a wide range of benchmark formulas. While CTL* is not widely used due to the complexity of its reasoning tasks, it is strictly more expressive than LTL or CTL. Furthermore, there are applications for theorem-proving and model-checking.

The Computational Tree Logic (CTL) has difficulty expressing some fairness properties. One solution is to instead use the syntactic extension Full CTL (CTL) or the more limited CTL+ extension, but either way the satisfiability problem then becomes doubly exponential. We discuss how the limit closure axiom of CTL makes representing fairness difficult. Removing this restriction results in Bundled CTL (BCTL). We present a singly exponential tableau for BCTL and show how BCTL can represent fairness properties in a similar way to CTL. We further show how to combine the BCTL tableau with an existing BCTL tableau, to give the full expressivity of BCTL while retaining a singly exponential running time when the number of BCTL operators is limited.

Lauchli and Leonard, in 1966, described a series of operations which are able to build all linear temporal structures up to first order equivalence. More recently these operations have been used to describe executions of continuous systems for the purposes of model checking real-time specifications. In this paper we present an algebra over these operations and show that it is both sound and complete, in that it can generate all equivalences over these models.

Temporal logics over general linear time allow us to capture continuous properties in applications such as distributed systems, natural language, message passing and A.I. modelling of human reasoning. Linear time structures, however, can exhibit a wide range of behaviours that are hard to reason with, or even describe finitely. Recently, a formal language of Model Expressions has been proposed to allow the convenient finite description of an adequately representative range of these generally infinite structures. Given a model described in this Model Expression language and a temporal logic formula, a model checking algorithm decides whether the formula is satisfied at some time in the model. Tools based on such algorithms would support a wide variety of tasks such as verification and counter-example investigation. A previous paper gave an exponential space algorithm for the problem of model checking Until/Since temporal formulas over linear time Model Expressions. Here we prove that the problem is actually PSPACE-complete. We present a new PSPACE algorithm and we show PSPACE-hardness by a reduction from quantified boolean formulas.

We introduce a new way of defining metric temporal logic over the continuous real model of time. The semantics refer to a single universal clock in order to impose metric constraints to any desired precision. Furthermore, the expression of any non-metric aspects can correctly utilise the full power of continuous time temporal logic. Syntactic constructs afford the convenient succinct expression of many useful and typical constraints while other, more intricate properties are able to be captured but may require more lengthy formulation. A decision procedure is provided via a simple translation into an existing non-metric temporal logic and this gives a workable complexity and the possibility of automated reasoning. There are advantages in expressiveness, naturalness, generality and amenability to reasoning techniques over the existing metric temporal logics. Combining purely continuous with adequate metric aspects in one language makes the logic very suitable for dealing with hybrid systems.

We use mosaics to provide a simple, sound, complete and terminating tableau reasoning procedure for the temporal logic of until and since over general linear time.

We use mosaics and games to provide a simple, sound and complete tableau reasoning procedure for the temporal logic of until and since over general linear time.

Abstract We present a sound, complete and implementable tableau method for deciding satisfiability of formulas in the propositional version of computation tree logic CTL*. This is the first such tableau. CTL* is an exceptionally important temporal logic with applications from hardware design to agent reasoning, but there is no easily automated reasoning approach to CTL*. The tableau here is a traditional tree-shaped or top-down style tableau, and affords the possibility of reasonably quick decisions on the satisfiability of medium-sized formulas and construction of small models for them. A straightforward subroutine is given for determining when looping allows successful branch termination, but much needed further development is left as future work. In particular, a more general repetition prevention mechanism is needed to speed up the task of tableau construction.

Impact analysis is an activity of assessing the effect of making a set of changes to a software system. Many approaches have been developed include performing impact analysis on a high level model that reflects to low level analysis using class interaction prediction. However, analysis from the model contains false results due to not all interactions between classes have impact to one another. In this paper we introduce a new impact analysis approach that is able to filter some false results using a set of impact prediction filters. The contributions of the paper are: (1) a new impact analysis approach; (2) a new set of impact prediction filters and; (3) evaluation results that show the new impact analysis approach improves the accuracy of the prediction results.

RoCTL* was proposed to model robustness in concurrent systems. RoCTL* extended CTL* with the addition of obligatory and robustly operators, which quantify over failure-free paths and paths with one more failure respectively. Whether RoCTL* is more expressive than CTL* has remained an open problem since the RoCTL* logic was proposed. We use the equivalence of LTL to counter-free automata to show that RoCTL* is expressively equivalent to CTL*; the translation to CTL* provides the first model checking procedure for RoCTL*. However, we show that RoCTL* is relatively succinct as all satisfaction preserving translations into CTL* are non-elementary in length.

This paper presents various semantic interpretations for logics of knowledge and time with prefect recall. We allow both past and future operators and examine the interpretation of different linear flows of time. In particular, we present temporal epistemic logics for each of the following flows of time: arbitrary linear orders; the integers; the rationals; the reals; and for uniform flows of time. (By uniform flows of time, we mean that time is an arbitrary linear order that is common knowledge to all agents). We propose axiomatizations for all logics except the last case, for which we show that no finite axiomatization can be found. The axiomatizations are shown to be sound and complete in the case of arbitrary linear orders and the rationals.

In this paper we consider the problem of temporal reasoning over a real numbers model of time. After a quick survey of related logics such as those based on intervals, or metric information or rational numbers, we concentrate on using the Until and Since temporal connectives introduced in. We will call this logic RTL. Although RTL has been axiomatized and is known to be decidable it has only recently been established that a PSPACE decision procedure exists. Thus, it is just as easy to reason over real-numbers time as over the traditional natural numbers model of time. The body of the paper outlines the basics of the novel temporal "mosaic" method used to show this complexity.

We present a sound, complete and relatively straightforward tableau method for deciding valid formulas in the propositional version of the bundled (or suffix and fusion closed) computation tree logic BCTL*. This proves that BCTL* is decidable. It is also moderately useful to have a tableau available for a reasonably expressive branching-time temporal logic. However, the main interest in this should be that it leads us closer to being able to devise a tableau-based technique for theorem-proving in the important full computational tree logic CTL*.

A new framework is presented for sensor network programming with situations. User requirements are expressed in terms of temporal and spatial constraints on the events observed by sensor network nodes. A novel spatial-temporal logic is introduced for this task. We also specify protocols for situation detection that can be executed on sensor nodes to meet those requirements. The feasibility of situation-based sensor network programming using our framework is illustrated by two examples: a temporal situation for recognising the occurrence of an explosion, and a spatial situation for detecting contours in a sensor node field.

Logics of general branching time, or historical necessity, have long been studied but important axiomatization questions remain open. Here the difficulties of finding axioms for such logics are considered and ideas for solving some of the main open problems are presented. A new, more expressive logical account is also given to support Peirce's prohibition on truth values being attached to the contingent future.

Abstract We give a sound and complete axiomatization for the full computation tree logic. CTL*, of R-generable models. This solves a long standing open problem in branching time temporal logic.

We study two‐dimensional Cartesian products of modal logics determined by infinite or arbitrarily long finite linear orders and prove a general theorem showing that in many cases these products are undecidable, in particular, such are the squares of standard linear logics like K4.3, S4.3, GL.3, Grz.3, or the logic determined by the Cartesian square of any infinite linear order. This theorem solves a number of open problems posed by Gabbay and Shehtman. We also prove a sufficient condition for such products to be not recursively enumerable and give a simple axiomatization for the square K4.3 × K4.3 of the minimal liner logic using non‐structural Gabbay‐type inference rules.

We continue in the same vein as O. Lichtenstein et al. (1985) in "The Glory of the Past", demonstrating the advantages of including past-time operators in using temporal logic in computer science. A normal form for temporal formulas, based on a simple combination of past formulas, is arrived at via syntactic rewrites and is shown to be a useful alternative to automata based temporal reasoning. The use of the normal form in providing a complete axiomatization for PCTL* (i.e. CTL* with past connectives) is sketched.

It is known that the tiling technique can be used to give simple proofs of undecidability of various two-dimensional modal and temporal logics. However, up until now, the simplest two-dimensional temporal logic, the compass logic of Venema, has eluded such treatment. We present a new coding of an enumeration of the tiling plane which enables us to show that the compass logic is undecidable.