Fairness, Assumptions, and Guarantees for Extended Bounded Response LTL+P Synthesis
1
Citation
20
Reference
10
Related Paper
Citation Trend
Keywords:
Realizability
Soundness
Completeness (order theory)
Realizability
Normalization
Cite
Citations (3)
Path checking, the special case of the model checking problem where the model under consideration is a single path, plays an important role in monitoring, testing, and verification. We prove that for linear-time temporal logic (LTL), path checking can be efficiently parallelized. In addition to the core logic, we consider the extensions of LTL with bounded-future (BLTL) and past-time (LTL+Past) operators. Even though both extensions improve the succinctness of the logic exponentially, path checking remains efficiently parallelizable: Our algorithm for LTL, LTL+Past, and BLTL+Past is in AC^1(logDCFL) \subseteq NC.
Parallelizable manifold
Succinctness
Cite
Citations (12)
Introduced by Dal Lago and Hofmann, quantitative realizability is a technique used to define models for logics based on Multiplicative Linear Logic. A particularity is that functions are interpreted as bounded time computable functions. It has been used to give new and uniform proofs of soundness of several type systems with respect to certain time complexity classes. We propose a reformulation of their ideas in the setting of Krivine's classical realizability. The framework obtained generalizes Dal Lago and Hofmann's realizability, and reveals deep connections between quantitative realizability and a linear variant of Cohen's forcing.
Realizability
Soundness
Forcing (mathematics)
Intuitionistic logic
Cite
Citations (1)
Linear temporal logic (LTL) has become a well established tool for specifying the dynamic behavior of reactive systems with an interleaving semantics and the automatatheoretic approach has proven to be a very useful mechanism for performing automatic verification in this setting. Especially alternating automata turned out to be a powerful tool in constructing efficient yet simple to understand decision procedures and directly yield on-the-fly model checking procedures. While this technique extends elegantly to richer domains where the underlying computations are modeled as (Mazurkiewicz) traces, it does so only for eventand location-based temporal logics. In this thesis, we exhibit a decision procedure for LTL over Mazurkiewicz traces which generalizes the classical automata-theoretic approach to a linear temporal logic interpreted no longer over sequences but restricted labeled partial orders. Specifically, we construct a (linear) alternating Buchi automaton accepting the set of linearizations of those traces satisfying the formula at hand. The salient point of our technique is to apply a notion of independencerewriting to formulas of the logic. Furthermore, we show that the class of linear and trace-consistent alternating Buchi automata corresponds exactly to LTL formulas over Mazurkiewicz traces, lifting a similar result from Loding and Thomas formulated in the framework of LTL over words. Additionally, a linear temporal logic with a different flavor is introduced as Foata linear temporal logic (LTLf). It is designed for specifying properties of synchronized systems that comprise clocked hardware circuits or Petri nets supplied with a maximal step semantics. Distributed synchronous transition systems (DSTSs) are introduced as formal models of these systems and are equipped with a Foata configuration graph-based semantics, which provides a link between these systems and the framework of Mazurkiewicz traces. To simplify the task of defining DSTSs, we introduce a simple calculus in the spirit of CCS. We give optimal decision procedures for satisfiability of LTLf formulas as well as for model checking, both based on alternating Buchi automata. The model checking procedure further employs an optimization which is similar to a technique known as partial order reduction.
Büchi automaton
TRACE (psycholinguistics)
Computation tree logic
Interleaving
Cite
Citations (10)
Linear Temporal Petri nets, which combine the advantages of Petri nets and temporal logic, can describe clearly and compactly causal and temporal relationships between the events of a system, including activity and safety. However, it is very important for model checking to reduce the size of the automata. For optimization the Buchi automata derived from LTL properties, it gives an improved method that applies rewriting the formula before translation, and then reduces the number of states generated by the translation via Boolean optimization.
Büchi automaton
Stochastic Petri net
Cite
Citations (0)
Introduced by Dal Lago and Hofmann, quantitative realizability is a technique used to define models for logics based on Multiplicative Linear Logic. A particularity is that functions are interpreted as bounded time computable functions. It has been used to give new and uniform proofs of soundness of several type systems with respect to certain time complexity classes. We propose a reformulation of their ideas in the setting of Krivine's classical realizability. The framework obtained generalizes Dal Lago and Hofmann's realizability, and reveals deep connections between quantitative realizability and a linear variant of Cohen's forcing.
Realizability
Soundness
Forcing (mathematics)
Cite
Citations (0)
Realizability
Soundness
Forcing (mathematics)
Intuitionistic logic
Cite
Citations (5)
We propose a proof system for reasoning on certain specifications of secure authentication systems. For this purpose, a new logic, sequence-indexed linear-time temporal logic (SLTL), is obtained semantically from standard linear-time temporal logic (LTL) by adding a sequence modal operator that represents a sequence of symbols. By this sequence modal operator, we can appropriately express message flows between clients and servers and states of servers in temporal reasoning. A Gentzen-type sequent calculus for SLTL is introduced, and the completeness and cut-elimination theorems for it are proved. SLTL is also shown to be PSPACE-complete and embeddable into LTL.
Sequence (biology)
Sequent
Modal operator
Completeness (order theory)
Computation tree logic
Operator (biology)
Cite
Citations (13)
Computation tree logic
Satisfiability
Signature (topology)
Cite
Citations (63)