Specification and encoding of transaction interaction properties

Transaction-level modeling is used in hardware design for describing designs at a higher level compared to the register-transfer level (RTL) (e.g. Cai and Gajski in CODES+ISSS ’03: proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, pp. 19–24, 2003; Chen et al. in FMCAD ’07: proceedings of the formal methods in computer aided design, pp. 53–61, 2007; Mahajan et al. in MEMOCODE ’07: proceedings of the 5th IEEE/ACM international conference on formal methods and models for codesign, pp. 123–132, 2007; Swan in DAC ’06: proceedings of the 43rd annual conference on design automation, pp. 90–92, 2006). Each transaction represents a unit of work, which is also a useful unit for design verification. In such models, there are many properties of interest which involve interactions between multiple transactions. Examples of this are ordering relationships in sequential processing and hazard checking in pipelined circuits. Writing such properties on the RTL design requires significant expertise in understanding the higher-level computation being done in a given RTL design and possible instrumentation of the RTL to express the property of interest. This is a barrier to the easy use of such properties in RTL designs.     

Edge Pricing of Multicommodity Networks for Selfish Users with Elastic Demands

We examine how to induce selfish heterogeneous users in a multicommodity network to reach an equilibrium that minimizes the social cost. In the absence of centralized coordination, we use the classical method of imposing appropriate taxes (tolls) on the edges of the network. We significantly generalize previous work (Yang and Huang in Transp. Res. Part B 38:1–15, [2004]; Karakostas and Kolliopoulos in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 268–276, [2004]; Fleischer et al. in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 277–285, [2004]) by allowing user demands to be elastic. In this setting the demand of a user is not fixed a priori but it is a function of the routing cost experienced, a most natural assumption in traffic and data networks. Research supported by MITACS and a NSERC Discovery grant.     

Polylog Space Compression,Pushdown Compression,and Lempel-Ziv Are Incomparable

The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation (Hariharan, S., & Shankar, P. in: Proceedings of the 2006 IEEE data compression conference, p. 453, 2006; League, C., & Eng, K. in: Proceedings of the 2007 IEEE data compression conference, pp. 272–282, 2007), and in particular calls for a formulation of information-lossless stack or pushdown compressors that allows a formal analysis of their performance and a more ambitious use of the stack in XML compression, where so far it is mainly connected to parsing mechanisms. In this paper we introduce the model of pushdown compressor, based on pushdown transducers that compute a single injective function while keeping the widest generality regarding stack computation.     

A Hierarchical and Contextual Model for Aerial Image Parsing

In this paper we present a hierarchical and contextual model for aerial image understanding. Our model organizes objects (cars, roofs, roads, trees, parking lots) in aerial scenes into hierarchical groups whose appearances and configurations are determined by statistical constraints (e.g. relative position, relative scale, etc.). Our hierarchy is a non-recursive grammar for objects in aerial images comprised of layers of nodes that can each decompose into a number of different configurations. This allows us to generate and recognize a vast number of scenes with relatively few rules. We present a minimax entropy framework for learning the statistical constraints between objects and show that this learned context allows us to rule out unlikely scene configurations and hallucinate undetected objects during inference. A similar algorithm was proposed for texture synthesis (Zhu et al. in Int. J. Comput. Vis. 2:107–126, 1998) but didn’t incorporate hierarchical information. We use a range of different bottom-up detectors (AdaBoost, TextonBoost, Compositional Boosting (Freund and Schapire in J. Comput. Syst. Sci. 55, 1997; Shotton et al. in Proceedings of the European Conference on Computer Vision, pp. 1–15, 2006; Wu et al. in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1–8, 2007)) to propose locations of objects in new aerial images and employ a cluster sampling algorithm (C4 (Porway and Zhu, 2009)) to choose the subset of detections that best explains the image according to our learned prior model. The C4 algorithm can quickly and efficiently switch between alternate competing sub-solutions, for example whether an image patch is better explained by a parking lot with cars or by a building with vents. We also show that our model can predict the locations of objects our detectors missed. We conclude by presenting parsed aerial images and experimental results showing that our cluster sampling and top-down prediction algorithms use the learned contextual cues from our model to improve detection results over traditional bottom-up detectors alone.     

Generalizing Inverse Compositional and ESM Image Alignment

Inverse compositional (IC) image alignment (Baker and Matthews in Int. J. Comput. Vis. 56(3):221–255, 2004) uses the symmetry between the roles of the fixed and moving images for faster processing. However, it requires implementation of compositional optimizer update steps. The IC approach can be viewed as an efficient way of computing the similarity measure derivative relative to the fixed image warp parameters. Since the mapping between the fixed and moving warp parameters is continuous and differentiable, this derivative can be converted into the moving warp space using the chain rule. This avoids the need for compositional update steps. Our generalization also allows the efficient second order method (ESM) (Malis in Proceedings of the 2004 IEEE International Conference on Robotics and Automation (ICRA04), pp. 1843–1848, 2004; Benhimane and Malis in IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004; Malis and Benhimane in Robot. Auton. Syst. 52(1):39–52, 2005) to be applied to general parameterizations of the transformation. Experiments using multiple similarity measures and optimizers show that our generalized IC method equals or exceeds the performance of the original IC approach. The generalized ESM approach is more reliable than the classic approach as it increases the capture radius of the optimization.     

Improved multi-processor scheduling for?flow time and?energy

Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805–813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409–420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647–659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m≥2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size.     

q-Families of CVD(MPFA) Schemes on General Elements: Numerical Convergence and the Maximum Principle

In this paper, families of flux-continuous, locally conservative, finite-volume schemes are presented for solving the general geometry-permeability tensor pressure equation on structured and unstructured grids in two and three dimensions. The schemes are applicable to the general tensor pressure equation with discontinuous coefficients and remove the O(1) errors introduced by standard reservoir simulation (two-point flux) schemes when applied to full anisotropic permeability tensor flow approximation (Edwards and Rogers in Multigrids Methods, vol. 1, pp. 190–200, 1993; Edwards and Rogers in Proceedings: 4th European Conference on the Mathematics of Oil Recovery, 1994; Edwards and Rogers in Comput. Geom. 2:259–290, 1998). Full tensors arise when the local orientation of the grid is non-aligned with the principal axes of the tensor field. Full tensors may also arise when fine scale permeability distributions are upscaled to obtain gridblock-scale permeability distributions. In general full tensors arise when using any structured or unstructured grid type that departs from K-orthogonality.     

Static and dynamic behaviour of gas bubbles in T-shaped non-clogging micro-channels

Preventing micro-channels from clogging is a major issue in most micro and nanofluidic systems (Gravesen et al., J Micromech Microeng 3(4):168–182, 1993; Jensen et al., In: Proc. of MicroTAS 2002, Nara, Japan, pp 733–735, 2002; Wong et al., J Fluid Mech 292:71–94, 1995). The T-shaped channel first reported by Kohnle et al. (In: IEEE MEMS, the 15th international IEEE micro electro mechanical conference (ed), Las Vegas, pp 77–80, 2002) prevents micro-channels from clogging by the aid of the equilibrium bubble position in such a geometry. This work is concerned with the static and dynamic behaviour of bubbles in such T-shaped micro-channels. The aspect ratio of a rectangle enclosing the T-shaped channel and the contact angle of the walls are the main parameters influencing the static and dynamic bubble behaviour. It is investigated in this article how these parameters relate to the equilibrium bubble shape and how optimum bubble velocities can be achieved inside the channel. An analytical model depending on the contact angle and the channel geometry is presented that allows to determine the bubble configuration inside the channel by minimizing the bubble’s surface energy. A second model is derived to predict the velocity of gas bubbles driven by buoyancy in vertical T-shaped channels. The model is applied to design T-shaped channels with a maximum mobility of gas bubbles. Experiments with MEMS fabricated devices and CFD simulations are used to verify the models. Furthermore design rules for an optimum non-clogging channel geometry which provides the highest gas bubble mobility are given.     

New Results on Web Caching with Request Reordering

We study web caching with request reordering. The goal is to maintain a cache of web documents so that a sequence of requests can be served at low cost. To improve cache hit rates, a limited reordering of requests is allowed. Feder et al. (Proceedings of the 13th ACM–SIAM Symposium on Discrete Algorithms, pp. 104–105, 2002), who recently introduced this problem, considered caches of size 1, i.e. a cache can store one document. They presented an offline algorithm based on dynamic programming as well as online algorithms that achieve constant factor competitive ratios. For arbitrary cache sizes, Feder et al. (Theor. Comput. Sci. 324:201–218, 2004) gave online strategies that have nearly optimal competitive ratios in several cost models.     

Image-based rendering of intersecting surfaces for dynamic comparative visualization

Nested or intersecting surfaces are proven techniques for visualizing shape differences between static 3D objects (Weigle and Taylor II, IEEE Visualization, Proceedings, pp. 503–510, 2005). In this paper we present an image-based formulation for these techniques that extends their use to dynamic scenarios, in which surfaces can be manipulated or even deformed interactively. The formulation is based on our new layered rendering pipeline, a generic image-based approach for rendering nested surfaces based on depth peeling and deferred shading.     

Model Checking Weighted Integer Reset Timed Automata

Weighted timed automata (WTA), introduced in Alur et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 49–62, Springer, Berlin, 2001), Behrmann et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 147–161, Springer, Berlin, 2001) are an extension of Alur and Dill (Theor. Comput. Sci. 126(2):183–235, 1994) timed automata, a widely accepted formalism for the modelling and verification of real time systems. Weighted timed automata extend timed automata by allowing costs on the locations and edges. There has been a lot of interest Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006), Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008), Brihaye et al. (Proceedings of FORMATS/FTRTFT’04, LNCS, vol. 3253, pp. 277–292, Springer, Berlin, 2004), Brihaye et al. (Inf. Comput. 204(3):408–433, 2006) in studying the model checking problem of weighted timed automata. The properties of interest are written using logic weighted CTL (WCTL), an extension of CTL with costs. It has been shown Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008) that the problem of model checking WTAs with a single clock using WCTL with no external cost variables is decidable, while 3 clocks render the problem undecidable Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006). The question of 2 clocks is open. In this paper, we introduce a subclass of weighted timed automata called weighted integer reset timed automata (WIRTA) and study the model checking problem. We give a clock reduction technique for WIRTA. Given a WIRTA A\mathcal{A} with n≥1 clocks, we show that a single clock WIRTA A￠\mathcal{A}' preserving the paths and costs of A\mathcal{A} can be obtained. This gives us the decidability of model checking WIRTA with n≥1 clocks and m≥1 costs using WCTL with no external cost variables. We then show that for a restricted version of WCTL with external cost variables, the model checking problem is undecidable for WIRTA with 3 stopwatch costs and 1 clock. Finally, we show that model checking WTA with 2 clocks and 1 stopwatch cost against WCTL with no external cost variables is undecidable, thereby answering a question that has remained long open.     

Local abstraction–refinement for the <Emphasis Type="Italic">μ</Emphasis>-calculus

A key technique for the verification of programs is counterexample-guided abstraction–refinement (CEGAR). Grumberg et al. (LNCS, vol 3385, pp. 233–249. Springer, Berlin, 2005; Inf Comput 205(8):1130–1148, 2007) developed a CEGAR-based algorithm for the modal μ-calculus. There, every abstract state is split in a refinement step. In this paper, the work of Grumberg et al. is generalized by presenting a new CEGAR-based algorithm for the μ-calculus. It is based on a more expressive abstract model and applies refinement only locally (at a single abstract state), i.e., the lazy abstraction technique for safety properties is adapted to the μ-calculus. Furthermore, it separates refinement determination from the (3-valued based) model checking. Three different heuristics for refinement determination are presented and illustrated.     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

Planar Polyline Drawings via Graph Transformations

We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where $W\leq\lfloor\frac{2n-2}{3}\rfloorWe study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universit?t Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where W ￡ ?\frac2n-23?W\leq\lfloor\frac{2n-2}{3}\rfloor , and W+H ￡ ?\frac4n-43?W+H\leq\lfloor \frac{4n-4}{3}\rfloor . It uses at most ?\frac2n-53?\lfloor\frac{2n-5}{3}\rfloor bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2).     

Ranking of fuzzy numbers by a new metric

In this paper, a new approach for comparison among fuzzy numbers based on new metric distance (D _TM) is proposed. All reasonable properties of ranking function are proved. At first, the distance on the interval numbers based on convex hall of endpoints is proposed. The existing distance measures for interval numbers, (Bardossy and Duckstein in Fuzzy rule-based modeling with applications to geophysical, biological and engineering systems. CRC press, Boca Raton, 1995; Diamond in Info Sci 46:141–157, 1988; Diamond and Korner in Comput Math Appl 33:15–32, 1997; Tran and Duckstein in Fuzzy Set Syst 130:331–341, 2002; Diamond and Tanaka Fuzzy regression analysis. In: Slowinski R (ed) Fuzzy sets in decision analysis, operations research and statistics. Kluwer, Boston, pp 349–387, 1998) do not satisfy the properties of a metric distance, while the proposed distance does. It is extended to fuzzy numbers and its properties are proved in detail. Finally, we compare the proposed definition with some of the known ones.     

All-Pairs Shortest Paths with Real Weights in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>3</Superscript>/log <Emphasis Type="Italic">n</Emphasis>) Time

We describe an O(n ³/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (SIAM J. Comput. 5:49–60, 1976), Takaoka (Inform. Process. Lett. 43:195–199, 1992), Dobosiewicz (Int. J. Comput. Math. 32:49–60, 1990), Han (Inform. Process. Lett. 91:245–250, 2004), Takaoka (Proc. 10th Int. Conf. Comput. Comb., Lect. Notes Comput. Sci., vol. 3106, pp. 278–289, Springer, 2004), and Zwick (Proc. 15th Int. Sympos. Algorithms and Computation, Lect. Notes Comput. Sci., vol. 3341, pp. 921–932, Springer, 2004). The new algorithm is surprisingly simple and different from previous ones. A preliminary version of this paper appeared in Proc. 9th Workshop Algorithms Data Struct. (WADS), Lect. Notes Comput. Sci., vol. 3608, pp. 318–324, Springer, 2005.     

Control of Robot Manipulators in Terms of Quasi-Velocities

In this paper we present new control algorithms for robots with dynamics described in terms of quasi-velocities (Kozłowski, Identification of articulated body inertias and decoupled control of robots in terms of quasi-coordinates. In: Proc. of the 1996 IEEE International Conference on Robotics and Automation, pp. 317–322. IEEE, Piscataway, 1996a; Zeitschrift für Angewandte Mathematik und Mechanik 76(S3):479–480, 1996c; Robot control algorithms in terms of quasi-coordinates. In: Proc. of the 34 Conference on Decision and Control, pp. 3020–3025, Kobe, 11–13 December 1996, 1996d). The equations of motion are written using spatial quantities such as spatial velocities, accelerations, forces, and articulated body inertia matrices (Kozłowski, Standard and diagonalized Lagrangian dynamics: a comparison. In: Proc. of the 1995 IEEE Int. Conf. on Robotics and Automation, pp. 2823–2828. IEEE, Piscataway, 1995b; Rodriguez and Kreutz, Recursive Mass Matrix Factorization and Inversion, An Operator Approach to Open- and Closed-Chain Multibody Dynamics, pp. 88–11. JPL, Dartmouth, 1998). The forward dynamics algorithms incorporate new control laws in terms of normalized quasi-velocities. Two cases are considered: end point trajectory tracking and trajectory tracking algorithm, in general. It is shown that by properly choosing the Lyapunov function candidate a dynamic system with appropriate feedback can be made asymptotically stable and follows the desired trajectory in the task space. All of the control laws have a new architecture in the sense that they are derived, in the so-called quasi-velocity and quasi-force space, and at any instant of time generalized positions and forces can be recovered from order recursions, where denotes the number of degrees of freedom of the manipulator. This paper also contains the proposition of a sliding mode control, originally introduced by Slotine and Li (Int J Rob Res 6(3):49–59, 1987), which has been extended to the sliding mode control in the quasi-velocity and quasi-force space. Experimental results illustrate behavior of the new control schemes and show the potential of the approach in the quasi-velocity and quasi-force space. Authors are with Chair of Control and Systems Engineering.     

A High Order Compact Scheme for the Pure-Streamfunction Formulation of the Navier-Stokes Equations

In this paper we continue the study, which was initiated in (Ben-Artzi et al. in Math. Model. Numer. Anal. 35(2):313–303, 2001; Fishelov et al. in Lecture Notes in Computer Science, vol. 2667, pp. 809–817, 2003; Ben-Artzi et al. in J. Comput. Phys. 205(2):640–664, 2005 and SIAM J. Numer. Anal. 44(5):1997–2024, 2006) of the numerical resolution of the pure streamfunction formulation of the time-dependent two-dimensional Navier-Stokes equation. Here we focus on enhancing our second-order scheme, introduced in the last three afore-mentioned articles, to fourth order accuracy. We construct fourth order approximations for the Laplacian, the biharmonic and the nonlinear convective operators. The scheme is compact (nine-point stencil) for the Laplacian and the biharmonic operators, which are both treated implicitly in the time-stepping scheme. The approximation of the convective term is compact in the no-leak boundary conditions case and is nearly compact (thirteen points stencil) in the case of general boundary conditions. However, we stress that in any case no unphysical boundary condition was applied to our scheme. Numerical results demonstrate that the fourth order accuracy is actually obtained for several test-cases.     

Speed-Up Theorems in Type-2 Computations Using Oracle Turing Machines

A classic result known as the speed-up theorem in machine-independent complexity theory shows that there exist some computable functions that do not have best programs for them (Blum in J. ACM 14(2):322–336, 1967 and J. ACM 18(2):290–305, 1971). In this paper we lift this result into type-2 computations. Although the speed-up phenomenon is essentially inherited from type-1 computations, we observe that a direct application of the original proof to our type-2 speed-up theorem is problematic because the oracle queries can interfere with the speed of the programs and hence the cancellation strategy used in the original proof is no longer correct at type-2. We also argue that a type-2 analog of the operator speed-up theorem (Meyer and Fischer in J. Symb. Log. 37:55–68, 1972) does not hold, which suggests that this curious speed-up phenomenon disappears in higher-typed computations beyond type-2. The result of this paper adds one more piece of evidence to support the general type-2 complexity theory under the framework proposed in Li (Proceedings of the Third International Conference on Theoretical Computer Science, pp. 471–484, 2004 and Proceedings of Computability in Europe: Logical Approach to Computational Barriers, pp. 182–192, 2006) and Li and Royer (On type-2 complexity classes: Preliminary report, pp. 123–138, 2001) as a reasonable setup.     

An earlier time for inserting and/or accelerating tasks

In a periodic real-time system scheduled by the EDF (Earliest Deadline First) algorithm (Liu and Layland, J. ACM 20(1), 40–61, 1973; Barauh, Proc. of the 27th IEEE International Real-Time Systems Symposium, 379–387, 2006; Buttazzo, J. Real-Time Syst. 29(1), 5–26, 2005), when new tasks have to be inserted into the system at run-time and/or current tasks request to increase their rates in response to internal or external events, the new sum of the utilizations after the insertion and/or acceleration should be limited, otherwise, one or more current tasks should usually be compressed (their periods being prolonged) in order to avoid overload. Buttazzo offered a time from which on this kind of adjustment can be done without causing any deadline miss in the system (Buttazzo et al., IEEE Trans. Comput. 51(3), 289–302, 2002). It is, however, not early enough. In this paper, an earlier time is given and formally proved.