1222159
The Fork Calculus
The Fork Calculus FC presents a theory of communicating systems in family with CCS, but it differs in the way that processes are put in parallel. In CCS there is a binary parallel operator |, and two processes p and q are put in parallel by p|q. In FC there is a unary fork operator, and a process p is activated to "run in parallel with the rest of the program" by fork(p). An operational semantics is defined, and a congruence relation between processes is suggested. In addition, a sound and complete axiomatisation of the congruence is provided. FC has been developed during an investigation of the programming language CML, an extension of ML with concurrency primitives, amongst them a fork operator.
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.
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.
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.
3252817
Optimal Strategies in Priced Timed Game Automata
Priced timed (game) automata extend timed (game) automata with costs on both locations and transitions. In this paper we focus on reachability priced timed game automata and prove that the optimal cost for winning such a game is computable under conditions concerning the non-zenoness of cost. Under stronger conditions (strictness of constraints) we prove that in case an optimal strategy exists, we can compute a state-based winning optimal strategy.
2737251
Better Bounds on the Accommodating Ratio for the Seat Reservation Problem
We investigate the problem of giving seat reservations on-line. We assume that a train travels from a start station to an end station, stopping at k stations, including the first and last. Passengers may attempt to make reservations at any point before they get on the train, and reservations can be made going from any station to any later station. All algorithms under consideration must be "fair", i.e., they are not allowed to reject a request for a reservation which could be made at the time. The "accommodating ratio" compares the performance of an on-line algorithm to that of the optimal off-line algorithm, under the assumption that the only sequences of requests allowed are sequences for which the optimal off-line algorithm could accommodate all requests. The train has a fixed number of seats, and we first consider the case in which all tickets have the same cost, and the seat reservation system attempts to maximize income. We prove improved upper bounds on the performance of First-Fit and Best-Fit, showing that in the worst case, neither algorithm does significantly better than any fair deterministic algorithm would. We also improve the upper bounds on the possible performance of any "fair" deterministic or randomized algorithm. A specific randomized algorithm is also considered. Finally, we consider the case in which the cost of a ticket is proportional to the distance traveled.
12699441
Fully abstract models for a process language with refinement
We study the use of sets of labelled partial orders (pomsets) as denotational models for process algebras. More specifically, we study their capability to capture degrees of nonsequentiality of processes. We present four full abstractness results. The operational equivalences are based on maximal action-sequences and step-sequences — defined for a very simple process language and its extensions with a refinement combinator (change of atomicity). The denotational models are all expressed as abstractions of a standard association of sets of labelled partial orders with processes.
17731673
Relaxed Balance through Standard Rotations
We consider binary search trees, where rebalancing transformations need not be connected with updates but may be delayed. For standard AVL tree rebalancing, we prove that even though the rebalancing operations are uncoupled from updates, their total number is bounded by O(M log(M+N)), where M is the number of updates to an AVL tree of initial size N. Hence, relaxed balancing of AVL trees comes at no extra cost asymptotically. Furthermore, our scheme differs from most other relaxed balancing schemes in an important aspect: No rebalancing transformation can be done in the wrong direction, i.e., no performed rotation can make the tree less balanced. Moreover, each performed rotation indeed corresponds to a real imbalance situation in the tree. Our results are important in designing efficient concurrency control strategies for main-memory databases. Main-memory search structures have gained new applications in large embedded systems, such as switching systems for mobile telephones.
13143397
On Grouping in Relational Algebra
The concept of grouping in relational algebra is well-known from its connection to aggregation. In this paper we generalize the grouping notion by defining a simultaneous grouping of more than one relation, and we discuss the application of operations on grouping elements other than just arithmetic aggregation. Finally we show that this grouping mechanism can be added to relational algebra without increasing its computational power.
5370976
Parametric Permutation Routing via Matchings
The problem of routing permutations on graphs via matchings is considered, and we present a general algorithm which can be parameterized by different heuristics. This leads to a framework which makes the analysis simple and local.