Narrow Results

We show that it is decidable whether a transitive mixed linear relation has an ω-chain. Using this result, we study a number of liveness verification problems for generalized timed automata within a unified framework. More precisely, we prove that (1) the mixed linear liveness problem for a timed automaton with dense clocks, reversal-bounded counters, and a free counter is decidable, and (2) the Presburger liveness problem for a timed automaton with discrete clocks, reversal-bounded counters, and a pushdown stack is decidable.

We show that the class of Event Clock Automata [2] admit a logical characterisation via an unrestricted monadic second order logic interpreted over timed words. The result is interesting in that it provides an unrestricted yet decidable logical characterisation of a non-trivial class of timed languages. A timed temporal logic considered earlier in the literature [11] is shown to be expressively complete with respect to the monadic logic.

Timed automata are commonly recognized as a formal behavioral model for real-time systems. For compositional system design, parallel composition of timed automata as proposed by Larsen et al. [22] is useful. Although parallel composition provides a general method for system construction, in the low level behavior, components often behave sequentially by passing control via communication. This paper proposes a behavioral model, named controller automata, to combine timed automata by focusing on the control passing between components. In a controller automaton, to each state a timed automaton is assigned. A timed automaton at a state may be preempted by the control passing to another state by a global labeled transition. A controller automaton properly extends the expressive power because of the stack, but this can make the reachability problem undecidable. Given a strict partial order over states, we show that this problem can be avoided and a controller automaton can be faithfully translated into a timed automaton.

The inclusion problem is one of the common problems in real-time systems. The general form of this problem is undecidable; however, the time-bounded verification of inclusion problem is decidable for timed automata. In this study, we propose a new discretization technique to verify the inclusion problem. The proposed technique is applied to a non-Zeno timed automaton with an upper bound that does not contain a non-reachable space for each transition. The new approach is based on the generation of timed bounded discretized language that represents an abstraction of timed words in the form of a set of a countable number of discrete timed words. A discrete timed word aggregates all timed words that share the same actions and their execution times that create the time continuous intervals. The lower and the upper bounds of an interval in a discrete timed word is defined by the minimum and maximum execution times associated to a given transition-run. In addition, we propose the verification schema of the inclusion between two timed bounded discretized languages generated by two non-Zeno timed automata.

We present an incremental algorithm for model checking the real-time systems against the requirements specified in the real-time extension of modal mu-calculus. Using this algorithm, we avoid the repeated construction and analysis of the whole state-space during the course of evolution of the system from time to time. We use a finite representation of the system, like most other algorithms on real-time systems. We construct and update a graph (called TSG) that is derived from the region graph and the formula. This allows us to halt the construction of this graph when enough nodes have been explored to determine the truth of the formula. TSG is minimal in the sense of partitioning the infinite state space into regions and it expresses a relation on the set of regions of the partition. We use the structure of the formula to derive this partition. When a change is applied to the timed automaton of the system, we find a new partition from the current partition and the TSG with minimum cost.

We introduce a generalization of tropical polyhedra able to express both strict and non-strict inequalities. Such inequalities are handled by means of a semiring of germs (encoding infinitesimal perturbations). We develop a tropical analogue of Fourier–Motzkin elimination from which we derive geometrical properties of these polyhedra. In particular, we show that they coincide with the tropically convex union of (non-necessarily closed) cells that are convex both classically and tropically. We also prove that the redundant inequalities produced when performing successive elimination steps can be dynamically deleted by reduction to mean payoff game problems. As a complement, we provide a coarser (polynomial time) deletion procedure which is enough to arrive at a simply exponential bound for the total execution time. These algorithms are illustrated by an application to real-time systems (reachability analysis of timed automata).

Software development for computer-supported cooperative work (CSCW) is a notoriously difficult task, involving often concurrent processes which are bound up with rigid timing constraints. To cope effectively with this difficulty, we propose in this paper the use of abstract finite-state models. The utility of these models is illustrated by encoding a CSCW system that we have built into finite-state automata, specifying in them a number of desired properties with temporal logic, and verifying these properties with model checking. By incorporating timing constraints into this process, we also gain insight into the usability of our system in real cooperative scenarios.

Web services privacy issues have been attracting more and more attention in the past years. Since the number of Web services-based business applications is increasing, the demands for privacy enhancing technologies for Web services will also be increasing in the future. In this paper, we investigate an extension of business protocols, i.e. the specification of which message exchange sequences are supported by the web service, in order to accommodate privacy aspects and time-related properties. For this purpose we introduce the notion of Timed Privacy-aware Business Protocols (TPBPs). We also discuss TPBP properties can be checked and we describe their verification process.

Many processes are characterized by high variability, making traditional process modeling languages cumbersome or even impossible to be used for their description. This is especially true in cooperative environments relying heavily on human knowledge. Declarative languages, like Declare, alleviate this issue by not describing what to do step-by-step but by defining a set of constraints between actions that must not be violated during the process execution. Furthermore, in modern cooperative business, time is of utmost importance. Therefore, declarative process models should be able to take this dimension into consideration. Timed Declare has already previously been introduced to monitor temporal constraints at runtime, but it has until now only been possible to provide an alert when a constraint has already been violated without the possibility of foreseeing and avoiding such violations. In this paper, we introduce an extended version of Timed Declare with a formal timed semantics for the entire language. The semantics degenerates to the untimed semantics in the expected way. We also introduce a translation to timed automata, which allows us to detect inconsistencies in models prior to execution and to early detect that a certain task is time sensitive. This means that either the task cannot be executed after a deadline (or before a latency), or that constraints are violated unless it is executed before (or after) a certain time. This makes it possible to use declarative process models to provide a priori guidance instead of just a posteriori detecting that an execution is invalid. We also outline how a Declare model with time can be used in resource planning and how Declare has been integrated into CPN Tools.

The main scope of this paper is the implementation of a method for production scheduling, using advanced model checking tools. This method makes use of timed automata in order to model complex production scheduling problems like the job-shop and the open-shop scheduling problems. By modeling scheduling problems using timed automata, feasible schedules correspond then to paths in the automata, while finding the optimum schedule corresponds to finding the shortest path in an automaton. Several algorithms and heuristics have been proposed to find the shortest paths in timed automata, which are mainly based on the implementation of graph algorithms that search the transition graph. In our work, an advanced model design and checking tool, called Uppaal, has been used to implement and test the above method on a number of different models and to show the effectiveness of such an approach in terms of finding optimal, or near to optimal, schedules in polynomial time, even for large scale problems.

Model-checking is an automatic technology for the verification of the temporal property of concurrent or real-time systems through explicit state exploration or implicit fix point computation. The systems are usually described by the automata and the properties of the systems are expressed by the temporal logic formula. The correctness of the real-time systems not only depends on logic result but also on the timing constraints. For the analysis of the real-time systems, we use timed automata and the LCTL which is the temporal extension of branching-time logic CTL to express the real-time systems and its properties respectively. Choosing dense domain instead of discrete domain may blow up the complexity of model-checking problem; in terms of Alur’s method, we can translate timed automata into region automata as a solution.