27807377
Protocol Feature Interactions
Feature interaction is one of the most intriguing problems in research and development of telecommunications systems. Features may interact and result in undesirable system behavior. Today the analysis of interactions is conducted in an ad hoc manner by subject matter experts. This leads to time-consuming feature design and testing without any interaction-free guarantee.
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.
38528864
Coping With Discontinuities In Computer Vision: Their Detection, Classification, And Measurement
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.
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. >
33611736
RAGOBOT: A New Platform for Wireless Mobile Sensor Networks
We present Ragobot, a fully-featured validated platform for use in mobile sensor networks. Ragobot is a robot of small dimensions with features that surpass those provided by many other robots in this category. Ragobot hardware and software are implemented with modularity as one of the main considerations; therefore, these are easy to upgrade and customize according to the needs of each specific application. Moreover, we present Ragoworld, a controlled physical space for the development and evaluation of mobile sensor network algorithms.
6127186
An efficient nearest neighbor search in high-dimensional data spaces
Similarity search in multimedia databases requires an efficient support of nearest neighbor search on a large set of high-dimensional points. A technique applied for similarity search in multimedia databases is to transform important properties of the multimedia objects into points of a high-dimensional feature space. The feature space is usually indexed using a multidimensional index structure. Then, similarity search corresponds to a range search which returns all objects within a threshold level of similarity to the query objects, and a k-nearest neighbor search that returns the k most similar objects to the query object. Initially, traditional multidimensional data structures (e.g., R-tree [1], kd-tree [5]), which were designed for indexing low-dimensional spatial data, were used for indexing high-dimensional feature vectors. However, recent research activities [10,9,8] reported
16831546
Neurobiology of decision making
Decision making is ubiquitous in our everyday life, and plays a central role in transforming a vast and complex array of incoming sensory stimuli to a meaningful sequence of purposeful actions. Many of these decisions have important biological consequences, whereas others may appear to have more limited impact. Despite their distinct subjective qualities, both external and internal cues can be used to guide the selection of a single choice from many possible alternatives. Often, such decisions display features of optimally tuned systems. The neural mechanisms that underpin such decision making are currently the subject of intense investigation in the cognitive and behavioral neurosciences. Papers published in this special issue reflect several trends that have contributed to the recent surge of interest in the neural basis of decision making. First, neuroscientists have begun to realize the benefits of decision-making models developed by mathematical psychologists in order to understand the neural basis of discrimination and categorization (Mazurek, Roitman, Ditterich, & Shadlen, 2003). Often referred to as rise-to-threshold models or diffusion models, they make a simplifying assumption that an action is triggered when the process of evidence accumulation reaches a certain threshold. Second, the importance of reward and reward expectations as determinants of both decision making and neural activity is increasingly appreciated. In particular, reinforcement learning and economic theories have provided valuable insights into the function of many brain structures (Lee, 2006; Schultz, 2006). Third, network models of decision making have begun to reflect a detailed knowledge of the biophysical mechanisms involved in synaptic transmission and the generation of action potentials (Wang, 2002). These models have the potential to explain how complex behavior, such as decision making, can arise from the dynamics of cortical and subcortical networks. Fourth, advances in neuroimaging techniques have further facilitated neurobiological studies of decision making by making it possible to investigate the neural basis of complex decision making in humans (Montague, King-Casas, & Cohen, 2006). Accordingly, the neurobiological study of decision making has become an exciting area of interdisciplinary investigation and collaboration, as demonstrated by many of the papers included here. Sensory discrimination tasks employing visual motion and tactile stimuli have provided a wealth of information about the nature of neural circuitry necessary to perform such
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.
2898745
The hausdorff voronoi diagram of polygonal objects: a divide and conquer approach
We study the Hausdorff Voronoi diagram of a set S of polygonal objects in the plane, a generalization of Voronoi diagrams based on the maximum distance of a point from a polygon, and show that it is equivalent to the Voronoi diagram of S under the Hausdorff distance function. We investigate the structural and combinatorial properties of the Hausdorff Voronoi diagram and give a divide and conquer algorithm for the construction of this diagram that improves upon previous results. As a byproduct we introduce the Hausdorff hull, a structure that relates to the Hausdorff Voronoi diagram in the same way as a convex hull relates to the ordinary Voronoi diagram. The Hausdorff Voronoi diagram finds direct application in the problem of computing the critical area of a VLSI Layout, a measure reflecting the sensitivity of a VLSI design to random manufacturing defects, described in a companion paper.13