Checking infinite-state systems is frequently done by encoding infinite sets of states as regular languages. Computing such a regular representation of, say, the set of reachable states of a system requires acceleration techniques that can finitely compute the effect of an unbounded number of transitions. Among the acceleration techniques that have been proposed, one finds both specific and generic techniques. Specific techniques exploit the particular type of system being analyzed, for example, a system manipulating queues or integers, whereas generic techniques only assume that the transition relation is represented by a finite-state transducer, which has to be iterated. In this article, we investigate the possibility of using generic techniques in cases where only specific techniques have been exploited so far. Finding that existing generic techniques are often not applicable in cases easily handled by specific techniques, we have developed a new approach to iterating transducers. This new approach builds on earlier work, but exploits a number of new conceptual and algorithmic ideas, often induced with the help of experiments, that give it a broad scope, as well as good performances.

This article considers finite-automata-based algorithms for handling linear arithmetic with both real and integer variables. Previous work has shown that this theory can be dealt with by using finite automata on infinite words, but this involves some difficult and delicate to implement algorithms. The contribution of this article is to show, using topological arguments, that only a restricted class of automata on infinite words are necessary for handling real and integer linear arithmetic. This allows the use of substantially simpler algorithms, which have been successfully implemented.

Abstract. Checking infinite-state systems is frequently done by encoding infinite sets of states as regular languages. Computing such a regular representation of, say, the reachable set of states of a system requires acceleration techniques that can finitely compute the effect of an unbounded number of transitions. Among the acceleration techniques that have been proposed, one finds both specific and generic techniques. Specific techniques exploit the particular type of system being analyzed, e.g. a system manipulating queues or integers, whereas generic techniques only assume that the transition relation is represented by a finite-state transducer, which has to be iterated. In this paper, we investigate the possibility of using generic techniques in cases where only specific techniques have been exploited so far. Finding that existing generic techniques are often not applicable in cases easily handled by specific techniques, we have developed a new approach to iterating transducers. This new approach builds on earlier work, but exploits a number of new conceptual and algorithmic ideas, often induced with the help of experiments, that give it a broad scope, as well as good performance. 1

Motivated by issues in temporal databases and in the verification of infinite-state systems, this talk considers the problem of representing periodic dense time information. Doing so requires handling a theory that combines discrete and continuous variables, since discrete variables are essential for representing periodicity. An automata-based approach for dealing with such a combined theory is thus introduced.

Translating linear temporal logic formulas to automata has proven to be an effective approach for implementing linear-time model-checking, and for obtaining many extensions and improvements to this verification method. On the other hand, for branching temporal logic, automata-theoretic techniques have long been thought to introduce an exponential penalty, making them essentially useless for model-checking. Recently, Bernholtz and Grumberg [1993] have shown that this exponential penalty can be avoided, though they did not match the linear complexity of non-automata-theoretic algorithms. In this paper, we show that alternating tree automata are the key to a comprehensive automata-theoretic framework for branching temporal logics. Not only can they be used to obtain optimal decision procedures, as was shown by Muller et al., but, as we show here, they also make it possible to derive optimal model-checking algorithms. Moreover, the simple combinatorial structure that emerges from the automata-theoretic approach opens up new possibilities for the implementation of branching-time model checking and has enabled us to derive improved space complexity bounds for this long-standing problem.

This paper is motivated by the fact that verifying liveness properties under a fairness condition is often problematic, especially when abstraction is used.It shows that using a more abstract notion than truth under fairness, specifically the concept of relative liveness property can lead to interesting possibilities.Technically, it is first established that deciding relative liveness is a PSPACE-complete problem and it is shown that relative liveness properties ca aiways be satisfied by some fair implementation.Thereafter, the interaction between behavior abstraction and relative Iiveness properties is studied and it is proved that relative liveness properties can be verified on behavior abstractions, if the abstracting homomorphism is simple in the sense of Ochsenschlager.

Partial-order methods make it possible to check properties of a concurrent system by state-space exploration without considering all interleavings of independent concurrent events. They have been applied to linear-time model checking, but so far only limited results are known about their applicability to branching-time model checking. In this paper, we introduce a general technique for lifting partial-order methods from linear-time to branching-time logics. This technique is shown to be applicable both to reductions that are applied to the structure representing the program before running the model checking procedure, as well as to reductions that can be obtained when model checking is done in an automata-theoretic framework. The latter are extended to branching-time logics by using the model-checking framework based on alternating automata introduced by O. Bernholtz et al. (1994).

A model-checking method for linear-time temporal logic that avoids the state explosion due to the modeling of concurrency by interleaving is presented. The method relies on the concept of the Mazurkiewicz trace as a semantic basis and uses automata-theoretic techniques, including automata that operate on words of ordinality higher than omega . In particular, automata operating on words of length omega *n, n in omega are defined. These automata are studied, and an efficient algorithm to check whether such automata are nonempty is given. It is shown that when it is viewed as an omega *n automaton, the trace automaton can be substituted for the production automaton in linear-time model checking. The efficiency of the method of P. Godefroid (Proc. Workshop on Computer Aided Verification, 1990) is thus fully available for model checking.>

peer reviewed

In this paper, we present a powerful framework for describing, storing, and reasoning about infinite temporal information. This framework is an extension of classical relational databases. It represents infinite temporal information by generalized tuples defined by linear repeating points and constraints on these points. We prove that relations formed from generalized tuples are closed under the operations of relational algebra. A characterization of the expressiveness of generalized relations is given in terms of predicates definable in Presburger arithmetic. Finally, we provide some complexity results.

Informal specifications of protocols are often imprecise and incomplete and are usually not sufficient to ensure the correctness of even very simple protocols. Consequently, formal specification methods, such as finite-state models, are increasingly being used. The selection/resolution (S/R) model is a finite-state model with a powerful communication mechanism that makes it easy to describe complex protocols as a collection of simple finite-state machines. A software environment, called SPANNER, has been developed to specify and analyze protocols specified with the S/R model. SPANNER provides the facility to compute the joint behavior of a number of finite-state machines and to check if the “product” machine has inaccessible states, states corresponding to deadlocks, and loops corresponding to livelocks. So far, however, SPANNER has had no facility to systematically deal with liveness conditions. For example, one might wish to specify that, although a communication channel is unreliable, a message will get through if it is sent infinitely often, and to check that the infinite behavior of the protocol viewed as an infinite sequence will always be in some ω-regular set (possibly specified in terms of a formula in temporal logic or as an ω-automata). In this paper we show that with very minor modifications to the implemented system it is possible to substantially extend the type of properties that can be specified and checked by SPANNER. This is done by extending the S/R model to include acceptance conditions found in automatons on infinite words, which permits the incorporation of arbitrary liveness conditions into the model. We show how these extensions can be easily incorporated into SPANNER (and into essentially any finite-state verification system) and how the resulting system is used to automatically verify the correctness of protocols.

We show that the class of properties of programs expressible in propositional temporal logic can be substantially extended if we assume the programs to be data-independent. Basically, a program is data-independent if its behavior does not depend on the specific data it operates upon. Our results significantly extend the applicability of program verification and synthesis methods based on propositional temporal logic.

Article Reasoning about fair concurrent programs Share on Authors: C Courcoubetis AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJView Profile , M Y Vardi IBM Almaden Research Center, Department K55/801, 650 Harry Road, San Jose, CA IBM Almaden Research Center, Department K55/801, 650 Harry Road, San Jose, CAView Profile , P Wolper AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 283–294https://doi.org/10.1145/12130.12159Online:01 November 1986Publication History 19citation247DownloadsMetricsTotal Citations19Total Downloads247Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Current Temporal Logics are all oriented towards the description of totally ordered sequences. This limits their usefulness for reasoning about systems whose computations cannot easily be mapped into totally ordered sequences. Here, we propose a temporal logic geared towards describing partially ordered sets and apply it to dynamic distributed systems. Even though the logic we define does not have the finite model property, we establish that it has a one exponential decision procedure and a complete axiomatization.

peer reviewed

In this paper, Propositional Temporal Logic (PTL) is applied to the specification and synthesis of the synchronization part of communicating processes.To specify a process, a PTL formula that describes its sequence of communications is given.The synthesis is done by constructing a model of the given specifications using a tableau-like satisfiability algorithm for PTL.This model can then be interpreted as a program.

We investigate extensions of temporal logic by finite automata on infinite words. There are three different types of acceptance conditions (finite, looping and repeating) that one can give for these finite automata. This gives rise to three different logics. It turns out, however. that these logics have the same expressive power but differ in the complexity of their decision problem. We also investigate the addition of alternation and show that it does not increase the complexity of the decision problem.

We apply an Extended Propositional Temporal Logic (EPTL) to the specification and synthesis of the synchronization part of communicating processes. To specify a process, we give an EPTL formula that describes its sequence of communications. The synthesis is done by constructing a model of the given specifications using a tableau-like satisfiability algorithm for the extended temporal logic. This model can then be interpreted as a program.

We start by proving that some properties of sequences are not expressible in Temporal Logic though they are expressible using for instance regular expressions. Then, we show how Temporal Logic can be extended to express any such property definable by a right-linear grammar and hence a regular expression, Finally, we give a decision procedure and complete axiomatization for the extended Temporal Logic.