52867515
Test Sequence Selection
We study the test sequence selection problem. Given a large number of tests for a protocol system, we want to select a subset of tests so that the number of tests is reduced yet the test coverage is not sacrificed. We discuss the complexity of the test selection problem and propose a class of algorithms for different protocol system information requirements, test coverage criteria, and cost. We report experimental results on ISDN connection control protocol system Q.931.
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. >
31110512
Discontinuity Detection and Thresholding-A Stochastic Approach
We study discontinuity detection and thresholding using a stochastic approach. We discuss a general form of detectors, which includes a number of well known detectors as special cases. Thresholding is indispensable to eliminate spurious responses from the detection process. We propose a Weighted Thresholding, which is designed to cope with a variety of anomalies. Our analysis and experimental results on real images show that intelligent thresholding methods can make a significant difference for discontinuity detection.
19220261
Path protection and blocking probability minimization in optical networks
We study the problem of shared path protection in optical networks from the viewpoint of blocking probability minimization. Unlike the worst-case approach common in other studies, which typically deals with one failure at a time and requires recomputation of the protection paths after every failure, our framework assumes a fixed path protection strategy for every connection that does not change in response to failures in other connections, which is more realistic for networks with high failure rates. We study backup-path strategy configurations that minimize the blocking probability and derive various properties. We show that configurations which do not have partial overlaps among connections backup paths are optimal in a rather general sense. We discuss the minmax optimal configuration properties and present an efficient algorithm for finding it in a case of special interest, while showing it to be NP-hard in general. In addition, we discuss the properties of the game resulting if each connection chooses its backup path selfishly; we show it to belong to the class of potential games, well-studied in the game theory literature, and derive several further properties resulting from its specific structure.
38528864
Coping With Discontinuities In Computer Vision: Their Detection, Classification, And Measurement
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. >
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.
8317522
A Web-Based Distributed Programming Environment
A Java-based system called the GeoJAVA System was introduced in [1]. This system allows a user to remotely compile his/her own C/C++ programs and execute them for visualization among a group of remote users. DISPE, which stands for DIStributed Programming Environment, expands on the GeoJAVA System by allowing the resulting executables to be run on systems other than the host on which they were compiled, thus making the system more versatile. DISPE uses Common Object Request Broker (CORBA) services to enable executables compiled on this system to invoke methods in libraries on remote sites in an architecturally heterogeneous environment. Not only does this allow users to compile and execute their programs remotely, but the maintenance and duplication of libraries is lowered since agents are used to search for symbols in libraries located remotely and to compile them with the user's source code. As long as there is an Internet connection between the hosts on which these libraries reside, the agents can search and compile with these libraries.
2778139
An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
We give the first linear-time algorithm for computing single-source shortest paths in a weighted interval or circular-arc graph, when we are given the model of that graph, i.e., the actual weighted intervals or circular-arcsand the sorted list of the interval endpoints. Our algorithm solves this problem optimally inO(n) time, wheren is the number of intervals or circular-arcs in a graph. An immediate consequence of our result is anO(qn + n logn)-time algorithm for the minimum-weight circle-cover problem, whereq is the minimum number of arcs crossing any point on the circle; then logn term in this time complexity is from a preprocessing sorting step when the sorted list of endpoints is not given as part of the input. The previously best time bounds were0(n logn) for this shortest paths problem, andO(qn logn) for the minimum-weight circle-cover problem. Thus we improve the bounds of both problems. More importantly, the techniques we give hold the promise of achieving similar (logn)-factor improvements in other problems on such graphs.
1444954
A New Class of Single Cycle T-Functions
T-function is a relatively new cryptographic building block suitable for streamciphers. It has the potential of becoming a substitute for LFSRs, and those that correspond to maximum length LFSRs are called single cycle T-functions. We present a family of single cycle T-functions, previously unknown. An attempt at building a hardware oriented streamcipher based on this new T-function is given.
14664253
A Bit-Width Optimization Methodology for Polynomial-Based Function Evaluation
We present an automated bit-width optimization methodology for polynomial-based hardware function evaluation. Due to the analytical nature of the approach, overflow protection and precision accurate to one unit in the last place (ulp) can be guaranteed. A range analysis technique based on computing the root of the derivative of a signal is utilized to determine the minimal number of integer bits. Fractional bit requirements are established using an analytical error expression derived from the functions that occur along the data path. Global fractional bit optimization across multiple computation stages is performed using simulated annealing and circuit area estimation functions