We show how inductive invariants can be used to solve coverability, boundedness and reachability problems for Petri nets. This approach provides algorithms that are conceptually simpler than previously published ones.
We show how inductive invariants can be used to solve coverability, boundedness and reachability problems for Petri nets. This approach provides algorithms that are conceptually simpler than previously published ones.
Many papers in the intersection of theoretical and applied algorithms show that the simple, asymptotically less efficient algorithm, performs better than the bestcomplex theoretical algorithms on random data or in spe...
详细信息
Many papers in the intersection of theoretical and applied algorithms show that the simple, asymptotically less efficient algorithm, performs better than the bestcomplex theoretical algorithms on random data or in specialized “real world” applications. This paper considers the Knuth–Morris–Pratt automaton, and shows a counter-intuitive practical result. The classical pattern matching paradigm is that of seeking occurrences of one string—the pattern, in another—the text, where both strings are drawn from an alphabet set Σ. Assuming the text length is n and the pattern length is m, this problem can naively be solved in time O(nm). In Knuth, Morris and Pratt’s seminal paper of 1977, an automaton, was developed that allows solving this problem in time O(n) for any alphabet. This automaton, which we will refer to as the KMP-automaton, has proven useful in solving many other problems. A notable example is the parameterized pattern matching model. In this model, a consistent renaming of symbols from Σ is allowed in a match. The parameterized matching paradigm has proven useful in problems in software engineering, computer vision, and other applications. It has long been believed that for texts where the symbols are uniformly random, the naive algorithm will perform as well as the KMP algorithm. In this paper, we examine the practical efficiency of the KMP algorithm versus the naive algorithm on a randomly generated text. We analyze the time under various parameters, such as alphabet size, pattern length, and the distribution of pattern occurrences in the text. We do this for both the original exact matching problem and parameterized matching. While the folklore wisdom is vindicated by these findings for the exact matching case, surprisingly, the KMP algorithm always works significantly faster than the naive in the parameterized matching case. We check this hypothesis for DNA texts and image data and observe a similar behavior as in the random text. We also show a very stru
Computer room cooling performance directly affect the operation of the engine room, the air conditioning out of the wind through the method to build a three-dimensional simulation of the engine room to explore the roo...
详细信息
ISBN:
(纸本)9783037856949
Computer room cooling performance directly affect the operation of the engine room, the air conditioning out of the wind through the method to build a three-dimensional simulation of the engine room to explore the room hotspot locations, and to optimize the configuration of the cabinet task according to the engine room heat distribution. Using the Fluent Fluid Dynamics processing software provides simple algorithm to simulate the flow and temperature fields of the simulation engine room, the idea of sampling point using the model output parameters, use the function fitting, build a function of the wind speed of the air speed sampling point obtained reasonable outlet velocity. In modern data centers, due to the cost and price of blade server is high and its small volume, it is widely used. Due to the energy and cooling conditions, the type of large-scale data center may need to spend millions of dollars each year, mainly for computing devices and systems required for cooling energy costs. Therefore it is necessary to improve data center equipment energy efficiency, maximize the energy efficiency of the data center and computing power.
暂无评论