6242554
Guided Synthesis of Control Programs Using UPPAAL
In this paper we address the problem of scheduling and synthesizing distributed control programs for a batch production plant. We use a timed automata model of the batch plant and the verification tool UPPAAL to solve the scheduling problem.In modeling the plant, we aim at a level of abstraction which is sufficiently accurate in order that synthesis of control programs from generated timed traces is possible. Consequently, the models quickly become too detailed and complicated for immediate automatic synthesis. In fact, only models of plants producing two batches can be analyzed directly! To overcome this problem, we present a general method allowing the user to guide the model-checker according to heuristically chosen strategies. The guidance is specified by augmenting the model with additional guidance variables and by decorating transitions with extra guards on these. Applying this method have made synthesis of control programs feasible for a plant producing as many as 60 batches.The synthesized control programs have been executed in a physical plant. Besides proving useful in validating the plant model and in finding some modeling errors, we view this final step as the ultimate litmus test of our methodology's ability to generate executable (and executing) code from basic plant models.
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.
5725449
Verification of an Audio Protocol with Bus Collision Using UPPAAL
In this paper we apply the tool Uppaal1 to an automatic analysis of a version of the Philips Audio Control Protocol with two senders and bus collision handling. This case study is significantly larger than the real-time/hybrid systems previously analysed by automatic tools. During the case study the tool Uppaal was extended with a new feature, committed locations, allowing efficient modelling of broadcast communication.
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.
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.
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.
945379
Fair versus Unrestricted Bin Packing

AbstractAbstract. We consider the on-line Dual Bin Packing problem where we have nunit size bins and a sequence of items. The goal is to maximize the number of items that are packed in the bins by an on-line algorithm. We investigate unrestrictedalgorithms that have the power of performing admission control on the items, i.e., rejecting items while there is enough space to pack them, versus fairalgorithms that reject an item only when there is not enough space to pack it. We show that by performing admission control on the items, we get better performance compared with the performance achieved on the fair version of the problem. Our main result shows that with an unfair variant of First-Fit, we can pack approximately two-thirds of the items for sequences for which an optimal off-line algorithm can pack all the items. This is in contrast to standard First-Fit where we show an asymptotically tight hardness result: if the number of bins can be chosen arbitrarily large, the fraction of the items packed by First-Fit comes arbitrarily close to five-eighths.

662314
Packet Bundling
When messages, which are to be sent point-to-point in a network, become available at irregular intervals, a decision must be made each time a new message becomes available as to whether it should be sent immediately or if it is better to wait for more messages and send them all together. Because of physical properties of the networks, a certain minimum amount of time must elapse in between the transmission of two packets. Thus, whereas waiting delays the transmission of the current data, sending immediately may delay the transmission of the next data to become available even more.We consider deterministic and randomized algorithms for this on-line problem, and characterize these by tight results under a new quality measure. It is interesting to note that our results are quite different from earlier work on the problem where the physical properties of the networks were emphasized less.
819414
Sort Order Problems in Relational Databases
A relation of degree k can be sorted lexicographically in k! different ways, i.e., according to any one of the possible permutations of the schema of the relation. Such permutations are referred to as sort orders. When evaluating unary and binary relational algebra operators using sort-merge algorithms, sort orders fulfilling the constraints enforced by the operators are chosen for the operand relations. The relations are then sorted according to their assigned sort orders, and the result is obtained by merging. Should the operands already be sorted according to one of the permissible sort orders, then only a merging is required. The sort order of the result will depend on the sort orders of the operands. When evaluating whole relational algebra expressions, the result of one operation will be used as an operand to the next. It is desirable to choose sort orders in such a way that the result of one operation will automatically fulfill the requirements of the next. In general, one would like to find a minimal number of operators in the expression for which this cannot be obtained, bearing in mind the overall goal of minimizing the total work. We show that this problem is NP-hard, and that the corresponding decision problem is NP-complete. However, most simplifications of the original problem give rise to efficient algorithms. In fact, most frequently occurring queries can be analyzed in linear time in the size of the query. This is due to the fact that only a very limited number of subsets of all permutations of schemas can be encountered in the algorithms, which means that compact representations for these subsets can be found.
19914316
Extending the Accommodating Function
The applicability of the accommodating function, a relatively new measure for the quality of on-line algorithms, is extended. If a limited amount n of some resource is available, the accommodating function A(?) is the competitive ratio when input sequences are restricted to those for which the amount ?n of resources suffices for an optimal off-line algorithm. The accommodating function was originally used only for ? ? 1. We focus on ? < 1, observe that the function now appears interesting for a greater variety of problems, and use it to make new distinctions between known algorithms and to find new ones.
20582368
AVL trees with relaxed balance
AVL trees with relaxed balance (G.M. Adel'son-Vel'skii et al., 1962) were introduced with the aim of improving runtime performance by allowing a greater degree of concurrency. This is obtained by uncoupling updating from rebalancing. We define a new collection of rebalancing operations which allows for a significantly greater degree of concurrency than the original proposal. Additionally, in contrast to the original proposal, we prove the complexity of the rebalancing. If N is the maximum size the tree could ever have, we prove that each insertion gives rise to at most /spl lsqb/log/sub /spl phi(N+3/2)+log/sub /spl phi(/spl radic/(5))/spl minus/3/spl rsqb/ rebalancing operations and that each deletion gives rise to at most /spl lsqb/log/sub /spl phi(N+3/2)+log/sub /spl phi(/spl radic/(5))/spl minus/4/spl rsqb/ rebalancing operations, where /spl phi/ is the golden ratio.<<ETX>>