2585986
Fast multiplication of a recursive block Toeplitz matrix by a vector and its application
We present an algorithm for multiplying an N × N recursive block Toeplitz matrix by a vector with cost O (N log N). Its application to optimal surface interpolation is discussed.
206832588
Optimization problems from feature testing of communication protocols
In feature testing of communication protocols, we want to construct a minimal number of tests with a desirable fault coverage. We model the protocols by extended finite state machines and reduce the test generation process to optimization problems on graphs. We study efficient algorithms and their complexity. We report experimental results on real systems, including Personal HandyPhone System, a 5ESS based ISDN wireless system, and 5ESS Intelligent Network Application Protocol.
38528864
Coping With Discontinuities In Computer Vision: Their Detection, Classification, And Measurement
206418940
Residual Analysis for Feature Detection
It is shown that in a very simple form residual analysis achieves results that are at least as good as if not better than those obtained by other techniques. There are many ways for extensions of the method. For example, moving average filters of regularization can be used to obtain the residual images. Also, the strength of the correlation, measured by D/sub rr/(O), can be used to eliminate noise, weak edges, etc. A more ambitious extension is by considering smoothing filters that leave invariant the function representing the reflectance from smooth surfaces. >
45853491
Testing Finite-State Machines: State Identification and Verification
We study the complexity of two fundamental problems in the testing of finite-state machines. 1) Distinguishing sequences (state identification). We show that it is PSPACE-complete to determine whether a finite-state machine has a preset distinguishing sequence. There are machines that have distinguishing sequences, but only of exponential length. We give a polynomial time algorithm that determines whether a finite-state machine has an adaptive distinguishing sequence. (The previous classical algorithms take exponential time.) Furthermore, if there is an adaptive distinguishing sequence, then we give an efficient algorithm that constructs such a sequence of length at most n(n/spl minus/1)/2 (which is the best possible), where n is the number of states. 2) Unique input output sequences (state verification). It is PSPACE-complete to determine whether a state of a machine has a unique input output sequence. There are machines whose states have unique input output sequences but only of exponential length. >
11856887
Approximation of linear functionals on a banach space with a Gaussian measure
Abstract We study approximation of linear functionals on separable Banach spaces equipped with a Gaussian measure. We study optimal information and optimal algorithms in average case, probabilistic, and asymptotic settings, for a general error criterion. We prove that adaptive information is not more powerful than nonadaptive information and that μ-spline algorithms, which are linear, are optimal in all three settings. Some of these results hold for approximation of linear operators. We specialize our results to the space of functions with continuous r th derivatives, equipped with a Wiener measure. In particular, we show that the natural splines of degree 2 r + I yield the optimal algorithms. We apply the general results to the problem of integration.
17000976
A Faster One-Dimensional Topological Compaction Algorithm
We consider the problem of one-dimensional topological compaction with jog insertions. Combining both geometric and graph theoretic approaches we present a faster and simpler algorithm, improving over previous results. The compaction algorithm takes as input a sketch consisting of a set F of features and a set W of wires, and minimizes the horizontal width of the sketch while maintaining its routability. The algorithm consists of the following steps: constructing a horizontal constraint graph, computing all possible jog positions, computing the critical path, relocating the features and reconstructing a new sketch homotopic to the input sketch suitable for detailed routing. The algorithm runs in O(|F| · |W|) worst-case time and space, which is asymptotically optimal in the worst case. Experimental results are also presented.
13517188
Computational geometry
Computational geometry [Edelsbrunner 1987; Preparata and Shamos 1985] evolves from the classical discipline of design and analysis of algorithms. It is concerned with the computational complexity of geometric problems that arise in various disciplines such as pattern recognition, computer graphics, computer vision, robotics, VLSI layout, operations research, statistics, and so on. In contrast with the classical approach to proving mathematical theorems about geometry-related problems, this discipline emphasizes the computational aspect of these problems and attempts to exploit the underlying geometric properties possible, for example, the metric space, to derive efficient algorithmic solutions. An objective of this discipline in the theoretical context is to study the intrinsic difficulty of geometric computation under a certain computation model and to devise provably efficient algorithms for the problems at hand. The measure of intrinsic difficulty of a geometric problem or efficiency of an algorithm is in terms of time and space complexities when the problem size tends to `. This is the so-called asymptotic computational complexity. Traditionally there are two types of complexity analysis of the asymptotic behavior of an algorithm: worst-case analysis and average-case analysis. In the former, the behavior of the algorithm with respect to the worst possible case of the input instance is considered, whereas in the latter, the expected behavior is considered when the input is randomly drawn from a given distribution. Recently the notion of randomized algorithms has emerged as an important area of study within algorithm design and analysis. Similar to average-case analysis, the analysis of randomized algorithms is also probabilistic with the exception that in the latter the input instance is fixed whereas the steps taken by the algorithm are random and governed by the outcomes of some probabilistic event, for example, the toss of a coin. Due to its applications to various science and engineering related disciplines, researchers in computational geometry have begun to address the efficacy of the algorithms; the issues concerning robustness and numerical stability [Fortune 1993] and the actual running times of their implementations have now become centers of attention as well. We concentrate here on the theoretical development of this field in the context of sequential computation. We adopt the real RAM (random-access machine) model of computation in which all arithmetic operations, comparisons, kth-root, exponential, or logarithmic functions take unit time. For more details refer to [Preparata and Shamos 1985]. Those who are interested in the implementations or would like more information about available software may consult the Proceedings of the Annual ACM Symposium on Computational Geometry, which has a video session, or the WWW page on Geometry in Action
41830429
An Optimal Algorithm for Roundness Determination on Convex Polygons
Abstract In tolerancing, the Out-Of-Roundness factor determines the relative circularity of planar shapes. The measurement of concern in this work is the Minimum Radial Separation, as recommended by the American National Standards Institute (ANSI). Here we show that the algorithm given in Le and Lee [6] runs in θ ( n 2 ) time even for convex polygons. Furthermore, we present an optimal O ( n ) time algorithm to compute the Minimum Radial Separation of convex polygons, which represents not only a factor n improvement over the previously best known algorithm, but also a factor of log n improvement over Le and Lee's conjectured complexity for the problem.
1430708
Towards a mechanized metatheory of standard ML
We present an internal language with equivalent expressive power to Standard ML, and discuss its formalization in LF and the machine-checked verification of its type safety in Twelf. The internal language is intended to serve as the target of elaboration in an elaborative semantics for Standard ML in the style of Harper and Stone. Therefore, it includes all the programming mechanisms necessary to implement Standard ML, including translucent modules, abstraction, polymorphism, higher kinds, references, exceptions, recursive types, and recursive functions. Our successful formalization of the proof involved a careful interplay between the precise formulations of the various mechanisms, and required the invention of new representation and proof techniques of general interest.
6192203
Authentication for Single/Multi Domain in Ubiquitous Computing Using Attribute Certification
The Ubiquitous computer environment is thing which invisible computer that is not shown linked mutually through network so that user may use computer always is been pervasive. Intend computing environment that can use easily as user wants and it is the smart environment that user provides context awareness that is wanting computing environment. This Ubiquitous computing contains much specially weak side in security. Masquerade attack of that crawl that is quoted to user or server among device that is around user by that discrete various computing devices exist everywhere among them become possible. Hereupon, in this paper, proposed method that has following characteristic. Present authentication model through transfer or device. Suggest two method that realize authentication through device in case of moved to method (MD: Multi Domain) and user ownself space (SD: Single Domain) that realize authentication through device in case of moved user's direct path who device differs.