Abstract $$\text {HyperLTL}$$ HyperLTL extends Linear Temporal Logic (LTL) with explicit trace variables and quantification over traces, allowing formulas to relate multiple executions within a single specification. Consequently, $$\text {HyperLTL}$$ HyperLTL has become an important specification formalism for hyperproperties, i.e., properties of sets of traces rather than individual traces. However, the satisfiability of $$\text {HyperLTL}$$ HyperLTL is undecidable, so fully automatic reasoning cannot, in general, replace deductive methods to establish validity. Furthermore, $$\text {HyperLTL}$$ HyperLTL restricts trace quantification to the outermost scope of formulas. In this paper, we study $$\text {HyperLTL} ^*$$ HyperLTL ∗ , a generalization that removes this restriction by allowing trace quantifiers to occur under temporal operators. We present a Gentzen-style sequent calculus for $$\text {HyperLTL} ^*$$ HyperLTL ∗ and establish completeness by means of suitable infinitary rules. We then derive sound finitary principles that are amenable to interactive theorem proving and can serve as a foundation for mechanized reasoning. We illustrate the use of the calculus on representative $$\text {HyperLTL}$$ HyperLTL -style specifications that are difficult to discharge by existing automatic procedures. Finally, we analyze the expressiveness of $$\text {HyperLTL} ^*$$ HyperLTL ∗ and discuss how the calculus can be combined with first-order reasoning infrastructure.

Recently we established an analog of Gabbay's separation theorem about linear temporal logic (LTL) for the extension of Moszkowski's discrete time propositional Interval Temporal Logic (ITL) by two sets of expanding modalities, namely the unary neighbourhood modalities and the binary weak inverses of ITL's chop operator. One of the many useful applications of separation in LTL is the concise proof of LTL's expressive completeness wrt the monadic first-order theory of 〈ω,<〉 it enables. In this paper we show how our separation theorem about ITL facilitates a similar proof of the expressive completeness of ITL with expanding modalities wrt the monadic first- and second-order theories of 〈Z,<〉.

Abstract We revisit the earliest temporal projection operator Π in discrete-time Propositional Interval Temporal Logic (PITL) and use it to formalise interleaving concurrency. The logical properties of Π as a normal modality and a way to eliminate it in both PITL and conventional point-based Linear-Time Temporal Logic (LTL), which can be viewed as a PITL subset, are examined, as are stutter-invariant formulas. Striking similarities between the expressiveness of Π and the standard LTL operator U (‘until’) are briefly illustrated. We also formalise concurrent imperative programming constructs with and without Π , and relate the two approaches. Peterson’s mutual exclusion algorithm is used to illustrate reasoning with Π about a concrete programming example. Projection with fairness and non-fairness assumptions are both discussed. This all illustrates an approach to the analysis of such concurrent interleaving finite-state systems using temporal logic formulas with projection constructs to reason about correctness properties. Unlike conventional LTL formulas about concurrency which normally largely focus on global time, properties expressed in LTL combined with Π help to reveal and analyse important differing viewpoints involving global time and the local projected time seen by each individual process. Links between Π and another standard PITL projection operator, both suitable for reasoning about different time granularities, are demonstrated by showing the two operators to be interdefinable. We briefly look at other (mostly interval-based) temporal logics with similar forms of projection, as well as some related applications and industrial standards.

We present a framework for evaluating and generating access control policies.The framework contains a modelling formalism called RW, which is supported by a model checking tool.RW is designed for modelling access control policies, and verifying their properties.The RW language is very expressive, allowing us to model complex access conditions which can depend on data values, other permissions, and agent roles.A property expresses the capability of a coalition of agents to achieve a goal, which may include reading and overwriting certain information.Given a model built based on a policy and a property, the model-checking algorithm decides whether the goal defined by the property is achievable by the coalition within the permissions the policy provides.In the case that the goal is achievable, the algorithm outputs strategies which may be used by the coalition to achieve the goal.The unachievability of legitimate goals may suggest that the policy does not provide the users enough permissions to carry out their actions.The achievability of malicious goals may reveal certain security holes in the policy.When malicious goals are achievable, the resulting strategies help to provide clues on amending the policy.The tool implements the algorithm and thus performs the RW model-checking.It can also convert a policy written in the RW language into a policy file in XACML.An access control system can then be built on the converted policy file.

We present a new proof of the fact that every formula in linear temporal logic with past is equivalent to a formula of the form ⋀i⋄□αi⇒⋄□βi, where αi

The paper presents probabilistic extensions of interval temporal logic (ITL) and duration calculus (DC) with infinite intervals and complete Hilbert-style proof systems for them. The completeness results are a strong completeness theorem for the system of probabilistic ITL with respect to an abstract semantics and a relative completeness theorem for the system of probabilistic DC with respect to real-time semantics. The proposed systems subsume probabilistic real-time DC as known from the literature. A correspondence between the proposed systems and a system of probabilistic interval temporal logic with finite intervals and expanding modalities is established too.

This paper presents an ω-complete proof system for the extension of first-order Interval Temporal Logic (ITL) by a projection operator. Alternative earlier approaches to the axiomatisation of projection in ITL are briefly presented and discussed. An extension of the proof system which is complete for the extension of Duration Calculus (DC) by projection is also given.