3246222
An Efficient Algorithm for Minimizing Real-time Transition Systems
We address the problem of performing simultaneously reachability analysis and minimization of real-time transition systems represented by timed automata , i.e., automata extended with a finite set of clock variables. The transitions of the automaton may depend on the values of the clocks and may reset some of the clocks. An efficient algorithm is presented for minimizing a system with respect to a given initial partition that respects the enabling conditions of the transitions of the timed automaton. Our algorithm generates the portion of the minimized system that is reachable from a given initial configuration in time polynomial in the input and the size of the minimal reachable system.
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.
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. >
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. >
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
3145025
Quantitative Evaluation of the Exploration Strategies of a Mobile Robot
This article describes an experimental investigation into the map-building and exploration capabilities of a mobile robot. Two types of map are used: a set of line and point features, and a grid-based free-space map. Potential features are ex tracted from sonar range readings and classed as "confirmed" if detected repeatedly. The free-space map is derived from the set of confirmed features. A distance-transform algorithm is then used to plan paths on this map. The confirmed features are used by a Kalman filter to estimate the robot's position relative to known objects. This research places exceptional stress on the need for practical experimentation and quantitative, statistical evaluation of the results. For this to be possible, it is essential to have a clearly defined measure of map quality. A novel metric is defined that predicts the effectiveness of the robot if it were to use the map to execute a set of test tasks. Exploration strategies are tested experimentally in a range of environments and starting positions. The results are eval uated and compared statistically. The tested strategies range from those that are totally reactive, such as wall-following, to those that use the developing map to focus attention on the un examined parts of the environment. The most promising results are observed from hybrid exploration strategies that combine the robustness of reactive navigation and the directive power of map-based strategies.
30142962
A study on contents distribution using electronic cash system
Electronic cash systems are used as payment tools of e-commerce. They should be equipped with independence, transferability, and dividability, which are requirements of digital rights management (DRM) servicing contents. The contents can be recognized in terms of money. Its concept applies to reprint, copy, and anonymous users. This paper shows DRM model which adopted e-cash as a result of examining requirements of e-cash and DRM. The DRM introduces the hierarchical structure, and gives anonymity to the contents or users. Lastly, several methods proposed are examined, compared and analyzed.
2528129
Rectilinear Paths Among Rectilinear Obstacles
We address problems of finding rectilinear paths among rectilinear obstacles subject to certain optimization criteria. They have applications in the fields of motion planning and computer-aided circuit design. The criteria that we consider include minimizing the length of the path, minimizing the number of bends on the path, bounding one of the two factors (length and number of bends) and minimizing the other, and minimizing a given non-decreasing function of both the length and the number of bends. The length measure of a rectilinear path can be the total length of all the segments of the paths or just the sum of lengths of all the vertical or horizontal segments of the path. Besides the various optimization criteria for the paths that we look for, the routing environments may have different constraints. For example, the obstacles can be rectangular or rectilinear, the orientations of the path may be restricted to be horizontal or vertical on different layers in a two-layer interconnection model, or the path can penetrate the obstacles and pay extra costs. Previous results and problem solving approaches are summarized and compared to ours in this dissertation. 
We obtain more efficient algorithms for finding a shortest rectilinear path between two points, minimum spanning tree of a set of points, and for finding assorted paths taking both length and the number of bends into consideration. We also derive a general problem transformation scheme to convert an instance in two-layer model into an equivalent problem in one-layer model, for which previously obtained algorithms under different objective functions are applicable.
17000769
On crossing minimization problem
In this paper, we consider a problem related to global routing postoptimization: the crossing minimization problem (CMP). Given a global routing representation, the CMP is to minimize redundant crossings between every pair of nets. In particular, there are two kinds of CMP: constrained CMP (CCMP) and unconstrained CMP (UCMP). These problems have been studied previously where an O(m/sup 2/n) algorithm was proposed for CCMP, and where an (mn/sup 2/+/spl xi//sup 2/) algorithm was proposed for UCMP where m is the total number of modules, n is the number of nets, and /spl xi/ is the number of crossings defined by an initial global routing topology. We present a simpler and faster O(mn) algorithm for CCMP and an O[n(m+/spl xi/)] time algorithm for UCMP. Both algorithms improve over the time bounds of the previously proposed algorithms. The novel part of our algorithm is that it uses the plane embedding information of globally routed nets in the routing area to construct a graph-based framework and obtain a good junction terminal assignment that minimizes the number of crossings.
15924002
On the Effectiveness of Relevance Profiling
Relevance profiling is a general process for withindocument retrieval. Given a query, a profile of retrieval status values is computed by sliding a fixed sized window across a document. In this paper, we report a series of bench experiments on relevance profiling, using an existing electronic book, and its associated book index. The book index is the source of queries and relevance judgements for the experiments. Three weighting functions based on a language modelling approach are investigated, and we demonstrate that the well-known query generation model outperforms one based on the Kullback-Leibler divergence, and one based on simple term frequency. The relevance profiling process proved highly effective in retrieving relevant pages within the electronic book, and exhibits stable performance over a range of sliding window sizes. The experimental study provides evidence for the effectiveness of relevance profiling for within-document retrieval, with the caveat that the experiment was conducted with a particular electronic book.