58171597
Compositional Model Checking of Real Time Systems
We present a compositional model checking technique for networks of timed automata. This method is based on the same idea as the recent method proposed by Andersen [4] for untimed case. We present a quotient construction, which allows timed automata components to be gradually moved from the network expression into the specification. The intermediate specifications are kept small using minimization heuristics suggested by Andersen. The potential of the combined technique is demonstrated using a prototype implemented in CAML.
4574615
As Cheap as Possible: Efficient Cost-Optimal Reachability for Priced Timed Automata
In this paper we present an algorithm for efficiently computing optimal cost of reaching a goal state in the model of Linearly Priced Timed Automata (LPTA). The central contribution of this paper is a priced extension of so-called zones. This, together with a notion of facets of a zone, allows the entire machinery for symbolic reachability for timed automata in terms of zones to be lifted to cost-optimal reachability using priced zones. We report on experiments with a cost-optimizing extension of Uppaal on a number of examples.
1457644
Time-Optimal Test Cases for Real-Time Systems
Testing is the primary software validation technique used by industry today, but remains ad hoc, error prone, and very expensive. A promising improvement is to automatically generate test cases from formal models of the system under test.
12983032
Practical verification of embedded software
Using a new verification algorithm called the compositional backward technique, the authors demonstrate that they can exhaustively verify even the largest industrial applications-comprising more than 1,000 components-in a few minutes on a standard PC.
14315022
Scaling up Uppaal Automatic Verification of Real-Time Systems Using Compositionality and Abstraction
To combat the state-explosion problem in automatic verification, we present a method for scaling up the real-time verification tool UPPAAL by complementing it with methods for abstraction and compositionality. We identify a notion of timed ready simulation which we show is a sound condition for preservation of safety properties between real-time systems, and in addition is a precongruence with respect to parallel composition. Thus, it supports both abstraction and compositionality. We furthermore present a method for automatically testing for the existence of a timed ready simulation between real-time systems using the UPPAAL tool.
8987497
Efficient Timed Reachability Analysis Using Clock Difference Diagrams
One of the major problems in applying automatic verification tools to industrial-size systems is the excessive amount of memory required during the state-space exploration of a model. In the setting of real-time, this problem of state-explosion requires extra attention as information must be kept not only on the discrete control structure but also on the values of continuous clock variables. 
 
In this paper, we exploit Clock Difference Diagrams, CDD's, a BDD-like data-structure for representing and effectively manipulating certain nonconvex subsets of the Euclidean space, notably those encountered during verification of timed automata. 
 
A version of the real-time verification tool Uppaal using CDD's as a compact data-structure for storing explored symbolic states has been implemented. Our experimental results demonstrate significant spacesavings: for eight industrial examples, the savings are in average 42% with moderate increase in runtime. 
 
We further report on how the symbolic state-space exploration itself may be carried out using CDD's.
406624
Model Checking Timed Automata with Priorities Using DBM Subtraction
In this paper we describe an extension of timed automata with priorities, and efficient algorithms to compute subtraction on DBMs (difference bounded matrices), needed in symbolic model-checking of timed automata with priorities. The subtraction is one of the few operations on DBMs that result in a non-convex set needing sets of DBMs for representation. Our subtraction algorithms are efficient in the sense that the number of generated DBMs is significantly reduced compared to a naive algorithm. The overhead in time is compensated by the gain from reducing the number of resulting DBMs since this number affects the performance of symbolic model-checking. The uses of the DBM subtraction operation extend beyond timed automata with priorities. It is also useful for allowing guards on transitions with urgent actions, deadlock checking, and timed games.
2795860
On-line seat reservations via off-line seating arrangements
When reservations are made to for instance a train, it is an on-line problem to accept or reject, i.e., decide if a person can be fitted in given all earlier reservations. However, determining a seating arrangement, implying that it is safe to accept, is an off-line problem with the earlier reservations and the current one as input. We develop algorithms with optimal running time to handle problems of this nature.
3019314
Amortized constant relaxed rebalancing using standard rotations
Abstract. The idea of relaxed balance is to uncouple the rebalancing in search trees from the updating in order to speed up request processing in main-memory databases. This paper defines the first relaxed binary search tree with amortized constant rebalancing using only standard single or double rotations.
28707658
Bounds on Certain Multiplications of Affine Combinations
Let A and B be n × n matrices the entries of which are affine combinations of the variables a1,…,am, b1,…,bm over GF(2). Suppose that, for each i, 1 ⩽ i ⩽ m, the term aibi is an element of the product matrix C = A · B. What is the maximum value that m can have as a function of n? This question arises from a recent technique for improving the communication complexity of zero-knowledge proofs. 
 
The obvious upper bound of n2 is improved to n233+ O(n). Tighter bounds are obtained for smaller values of n. The bounds for n = 2, n = 3, and n = 4 are tight.
13526164
The Maximum Resource Bin Packing Problem
Usually, for bin packing problems, we try to minimize the number of bins used or in the case of the dual bin packing problem, maximize the number or total size of accepted items. This paper presents results for the opposite problems, where we would like to maximize the number of bins used or minimize the number or total size of accepted items. We consider off-line and on-line variants of the problems. 
 
For the off-line variant, we require that there be an ordering of the bins, so that no item in a later bin fits in an earlier bin. We find the approximation ratios of two natural approximation algorithms, First-Fit-Increasing and First-Fit-Decreasing for the maximum resource variant of classical bin packing. 
 
For the on-line variant, we define maximum resource variants of classical and dual bin packing. For dual bin packing, no on-line algorithm is competitive. For classical bin packing, we find the competitive ratio of various natural algorithms. 
 
We study the general versions of the problems as well as the parameterized versions where there is an upper bound of $\frac{1}{k}$ on the item sizes, for some integer k.