25305779
Priority Algorithms for Graph Optimization Problems
We continue the study of priority or “greedy-like” algorithms as initiated in [6] and as extended to graph theoretic problems in [9]. Graph theoretic problems pose some modelling problems that did not exist in the original applications of [6] and [2]. Following [9], we further clarify these concepts. In the graph theoretic setting there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known “greedy algorithms”.
80794
Efficient Rebalancing of Chromatic Search Trees
Chromatic trees were defined by Nurmi and Soisalon-Soininen, as a new type of binary search tree for databases. The aim is to improve runtime performance by allowing a greater degree of concurrency, which, in turn, is obtained by uncoupling updating from rebalancing. This also allows rebalancing to be postponed completely or partially until after peak working hours. The advantages of the proposal of Nurmi and Soisalon-Soininen are quite significant, but there are definite problems with it. First, they give no explicit upper bound on the complexity of their algorithm. Second, some of their rebalancing operations can be applied many more times than necessary. Third, some of their operations, when removing one problem, create another. We define a new set of rebalancing operations which we prove give rise to at most @?log"2(N+1)@?-1 rebalancing operations per insertion and at most @?log"2(N+1)@?-2 rebalancing operations per deletion, where N is the maximum size the tree could ever have, given its initial size and the number of insertions performed. Most of these rebalancing operations, in fact, do no restructuring; they simply move weights around. The number of operations which actually change the structure of the tree is at most one per update.
30882911
Complexity of Layered Binary Search Trees with Relaxed Balance
When search trees are made relaxed, balance constraints are weakened such that updates can be made without immediate rebalancing. This can lead to a speed-up in some circumstances. However, the weakened balance constraints also make it more challenging to prove complexity results for relaxed structures.In our opinion, one of the simplest and most intuitive presentations of balanced search trees has been given via layered trees. We show that relaxed layered trees are among the best of the relaxed structures. More precisely, rebalancing is worst-case logarithmic and amortized constant per update, and restructuring is worst-case constant per update.
6986183
Efficient Simplification of Bisimulation Formulas
The problem of checking or optimally simplifying bisimulation formulas is likely to be computationally very hard. We take a different view at the problem: we set out to define a very fast algorithm, and then see what we can obtain. Sometimes our algorithm can simplify a formula perfectly, sometimes it cannot. However, the algorithm is extremely fast and can, therefore, be added to formula-based bisimulation model checkers at practically no cost. When the formula can be simplified by our algorithm, this can have a dramatic positive effect on the better, but also more time consuming, theorem provers which will finish the job.
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.
34233329
Search Trees with Relaxed Balance and Near-Optimal Height
We introduce the relaxed k-tree, a search tree with relaxed balance and a height bound, when in balance, of (1 + Ɛ) log2 n + 1, for any Ɛ > 0. The rebalancing work is amortized O(1/Ɛ) per update. This is the first binary search tree with relaxed balance having a height bound better than c ċ log2 n for a fixed constant c. In all previous proposals, the constant is at least 1/ log2 Φ > 1.44, where Φ is the golden ratio. 
 
As a consequence, we can also define a standard (non-relaxed) k-tree with amortized constant rebalancing per update, which is an improvement over the original definition. 
 
Search engines based on main-memory databases with strongly fluctuating workloads are possible applications for this line of work.
189953
Verification of Hierarchical State/Event Systems using Reusability and Compositionality
We investigate techniques for verifying hierarchical systems, i.e., finite state systems with a nesting capability. The straightforward way of analysing a hierarchical system is to first flatten it into an equivalent non-hierarchical system and then apply existing finite state system verification techniques. Though conceptually simple, flattening is severely punished by the hierarchical depth of a system. To alleviate this problem, we develop a technique that exploits the hierarchical structure to reuse earlier reachability checks of superstates to conclude reachability of substates. We combine the reusability technique with the successful compositional technique of J. Lind-Nielsen, H.R. Andersen, G. Behrmann, H. Hulgaard, K. Kristoffersen, and K.G. Larsen, 1998. In: Tools and Algorithms for the Construction and Analysis of Systems, Vol. 1384 of Lecture Notes in Computer Science, pp. 201–216, and investigate the combination experimentally on industrial systems and hierarchical systems generated according to our expectations to real systems. The experimental results are very encouraging: whereas a flattening approach degrades in performance with an increase in the hierarchical depth (even when applying the technique of J. Lind-Nielsen et al. (1998)), the new approach proves not only insensitive to the hierarchical depth, but even leads to improved performance as the depth increases.
18794799
Model-Checking for Real-Time Systems
Efficient automatic model-checking algorithms for real-time systems have been obtained in recent years based on the state-region graph technique of Alur, Courcoubetis and Dill. However, these algorithms are faced with two potential types of explosion arising from parallel composition: explosion in the space of control nodes, and explosion in the region space over clock-variables.
11147632
Lower and upper bounds in zone-based abstractions of timed automata
Timed automata have an infinite semantics. For verification purposes, one usually uses zone-based abstractions w.r.t. the maximal constants to which clocks of the timed automaton are compared. We show that by distinguishing maximal lower and upper bounds, significantly coarser abstractions can be obtained. We show soundness and completeness of the new abstractions w.r.t. reachability and demonstrate how information about lower and upper bounds can be used to optimise the algorithm for bringing a difference bound matrix into normal form. Finally, we experimentally demonstrate that the new techniques dramatically increase the scalability of the real-time model checker UPPAAL.
8200399
Compositional and symbolic model-checking of real-time systems
Efficient automatic model-checking algorithms for real-time systems have been obtained in recent years based on the state-region graph technique of Alur, Courcoubetis and Dill (1990). However, these algorithms are faced with two potential types of explosion arising from parallel composition: explosion in the space of control nodes, and explosion in the region space over clock-variables. In this paper we attack these explosion problems by developing and combining compositional and symbolic model-checking techniques. The presented techniques provide the foundation for a new automatic verification tool UPPAAL. Experimental results indicate that UPPAAL performs time- and space-wise favorably compared with other real-time verification tools.
120343602
The power of reachability testing for timed automata
The computational engine of the verification tool UPPALL consists of a collection of efficient algorithms for the analysis of teachability properties of systems. Model-checking of properties other than plain reachability ones may currently be carried out in such a tool as follows. Given a property φ to model-check, the user must provide a test automaton Tφ for it. This test automaton must be such that the original system S has the property expressed by φ precisely when none of the distinguished reject states of Tφ can be reached in the synchronized parallel composition of S with Tφ. This raises the question of which properties may be analysed by UPPAAL in such a way. This paper gives an answer to this question by providing a complete characterization of the class of properties for which model-checking can be reduced to reachability testing in the sense outlined above. This result is obtained as a corollary of a stronger statement pertaining to the compositionality of the property language considered in this study. In particular, it is shown that our language is the least expressive compositional language that can express a simple safety property stating that no reject state can ever be reached.Finally, the property language characterizing the power of reachability testing is used to provide a definition of characteristics properties with respect to a timed version of the ready simulation preorder, for nodes of τ-free, deterministic timed automata.