27033090
Exponentially Decreasing Number of Operations in Balanced Trees
While many tree-like structures have been proven to support amortized constant number of operations after updates, considerably fewer structures have been proven to support the more general exponentially decreasing number of operations with respect to distance from the update. In addition, all existing proofs of exponentially decreasing operations are tailor-made for specific structures. We provide the first formalization of conditions under which amortized constant number of operations imply exponentially decreasing number of operations. Since our proof is constructive, we obtain the constants involved immediately. Moreover, we develop a number of techniques to improve these constants.
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.
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.
43259181
Exponentially decreasing number of operations in balanced trees
While many tree-like structures have been proven to support amortized constant number of operations after updates, considerably fewer structures have been proven to support the more general exponentially decreasing number of operations with respect to distance from the update. In addition, all existing proofs of exponentially decreasing operations are tailor-made for specific structures. We provide the first formalization of conditions under which amortized constant number of operations imply exponentially decreasing number of operations. Since our proof is constructive, we obtain the constants involved immediately. Moreover, we develop a number of techniques to improve these constants.
2070879
Injectivity of Composite Functions
The problem of deciding injectivity of functions is addressed. The functions under consideration are compositions of more basic functions for which information about injectivity properties is available. We present an algorithm which will often be able to prove that such a composite function is injective. This algorithm constructs a set of propositional Horn clause axioms from the function specification and the available information about the basic functions. The existence of a proof of injectivity is then reduced to the problem of propositional Horn clause deduction. Dowling and Gallier have designed several very fast algorithms for this problem, the efficiency of which our algorithm inherits. The proof of correctness of the algorithm amounts to showing soundness and completeness of the generated Horn clause axioms.
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.
3021700
Minimum-Cost Reachability for Priced Timed Automata
This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them.
336650
UPPAAL 4.0
UPPAAL 4.0 is the result of over two and a half years of development and contains many new features, additions to the modeling language, performance improvements, enhancements and polish to the easy to use graphical user interface, and is accompanied by several open source libraries. The tool and libraries are available free of charge for academic, educational and evaluation purposes from http://www.uppaal.com/. We describe three of the new features: user defined functions, priorities and symmetry reduction
6620376
Time-abstracted Bisimulation: Implicit Specifications and Decidability
In the last few years a number of real-time process calculi have emerged with the purpose of capturing important quantitative aspects of real-time systems. In addition, a number of process equivalences sensitive to time-quantities have been proposed, among these the notion of timed (bisimulation) equivalence in [RR86, DS89, HR91, BB89, NRSV90, MT90, Wan91b].
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.
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.