Search

Given several number sequences, determining the longest common subsequence is a classical problem in computer science. This problem has applications in bioinformatics, especially determining transposable genes. Nevertheless, related works only consider how to find one longest common subsequence. In this paper, we consider how to determine the uniqueness of the longest common subsequence. If there are multiple longest common subsequences, we also determine which number appears in all/some/none of the longest common subsequences. We focus on four scenarios: (1) linear sequences without duplicated numbers; (2) circular sequences without duplicated numbers; (3) linear sequences with duplicated numbers; (4) circular sequences with duplicated numbers. We develop corresponding algorithms and apply them to gene sequencing data. [ABSTRACT FROM AUTHOR]

This paper focuses on image filtering using weighted median (WM) filters, a nonlinear filter class taking advantages of the robust order-statistic theory and capability to adapt a filter behavior for a variety of statistics related to the desired signals and the noise distributions. The main contribution of the paper is the analysis of the four WM optimization schemes, namely genetic WM optimization, non-adaptive WM optimization algorithm and adaptive WM filtering utilizing the linear and the sigmoidal approximation of the sign function. The analysis is done by extensive simulations, in which several features such as noise reduction, edge preservation, error estimation and dependence of error criteria on the degree of the impulse noise corruption, are examined. [ABSTRACT FROM AUTHOR]

In this paper, a self-stabilizing algorithm is presented for finding the articulation points of a connected undirected graph on a distributed or network model of computation after O(n[SUP2]|E|) moves. The algorithm is resilient to transient faults and does not require initialization. A correctness proof of the algorithm is also presented. The paper concludes with remarks on issues such as the time complexity of the algorithm and open problems. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the adiabatic evolution of one-dimensional projector Hamiltonians. Three kinds of adiabatic algorithms for this problem are shown, in which two of them provide a quadratic speedup over the other one. But when the ground state of the initial Hamiltonian and that of the final Hamiltonian have a zero overlap, the algorithms above all fail, in the sense of infinite time complexity. A corresponding revised method for this phenomenon through adding a driving Hamiltonian is also shown, from which a constant time complexity can be gained. But by a simple analysis, we find that the original time complexity for the adiabatic evolution is shifted to implement the driving Hamiltonian, which is supported by several early works in the literature. [ABSTRACT FROM AUTHOR]

Document clustering is one of the most effective techniques to organize documents in an unsupervised manner. In this paper, an Incremental method for document Clustering based on Information Bottleneck theory (ICIB) is presented. The ICIB is designed to improve the accuracy and efficiency of document clustering, and resolve the issue that an arbitrary choice of document similarity measure could produce an inaccurate clustering result. In our approach, document similarity is calculated using information bottleneck theory and documents are grouped incrementally. A first document is selected randomly and classified as one cluster, then each remaining document is processed incrementally according to the mutual information loss introduced by the merger of the document and each existing cluster. If the minimum value of mutual information loss is below a certain threshold, the document will be added to its closest cluster; otherwise it will be classified as a new cluster. The incremental clustering process is low-precision and order-dependent, which cannot guarantee accurate clustering results. Therefore, an improved sequential clustering algorithm (SIB) is proposed to adjust the intermediate clustering results. In order to test the effectiveness of ICIB method, ten independent document subsets are constructed based on the 20NewsGroup and Reuters-21578 corpora. Experimental results show that our ICIB method achieves higher accuracy and time performance than K-Means, AIB and SIB algorithms. [ABSTRACT FROM AUTHOR]

We introduce in this paper a new type of extended attribute reduction called M-reducts for an inconsistent decision table, which is defined to preserve the membership degree to a maximum decision class for each object of the table. It is shown that a M-reduct can actually preserve more decision information than it does by definition, including the maximum decision class itself and all deterministic decision information. Compared with other types of extended attribute reductions, the proposed type of attribute reduction is a better trade-off between the knowledge preserving capability and reduction efficiency. Illustrative examples are given and an effective algorithm for computing a M-reduct based on two summation functions of attribute sets is proposed together with its complexity analysis. [ABSTRACT FROM AUTHOR]

This paper presents a new approach, known as symmetry axis based feature extraction and recognition (SAFER), for recognizing objects under translation, rotation and scaling. Unlike most previous invariant object recognition (IOR) systems, SAFER puts emphasis on both simplicity and accuracy of the recognition system. To achieve simplicity, it uses simple formulae for extracting invariant features from an object. The scheme used in feature extraction is based on the axis of symmetry and angles of concentric circles drawn around the object. SAFER divides the extracted features into a number of groups based on their similarity. To improve the recognition performance, SAFER uses a number of neural networks (NNs) instead of single NN are used for training and recognition of extracted features. The new approach, SAFER, has been tested on two of real world problems i.e., English characters with two different fonts and images of different shapes. The experimental results show that SAFER can produce good recognition performance in comparison with other algorithms. [ABSTRACT FROM AUTHOR]

As is well-known, Axel Thue constructed an infinite word over a 3-letter alphabet that contains no squares, that is, no nonempty subwords of the form xx. In this paper we consider a variation on this problem, where we try to avoid approximate squares, that is, subwords of the form xx' where |x| = |x'| and x and x' are "nearly" identical. [ABSTRACT FROM AUTHOR]

For a string w ∈ {0,1, 2,..., d-1}*, let vald(w) denote the integer whose base d representation is the string w and let MSDd(x) denote the most significant or the leading digit of a positive integer x when x is written as a base d integer. Hirvensalo and Karhumäki [9] studied the problem of computing the leading digit in the ternary representation of 2x ans showed that this problem has a polynomial time algorithm. In [16], some applications are presented for the problem of computing the leading digit of AB for given inputs A and B. In this paper, we study this problem from a formal language point of view. Formally, we consider the language Lb,d,j = {w|w ∈ {0,1, 2,..., d-1}*, 1 ≤ j ≤ 9, MSDb(dvalb(w))) = j} (and some related classes of languages) and address the question of whether this and some related languages are context-free. Standard pumping lemma proofs seem to be very difficult for these languages. We present a unified and simple combinatorial technique that shows that these languages are not unambiguous context-free languages. The Benford-Newcomb distribution plays a central role in our proofs. [ABSTRACT FROM AUTHOR]

In this paper we propose a new definition of gradual dependence as a special kind of association rule. We propose a way to adapt existing association rule mining algorithms for the new task of mining such dependencies, and we discuss about its complexity. Some experiments in a real database illustrate the usefulness of the approach. [ABSTRACT FROM AUTHOR]

Sense of direction is a property of the edge-labeling of a network whose availability facilitates computations and often decreases their complexity. In this paper we consider the problem of providing a sense of direction to an anonymous, unoriented torus. The edges of the torus are initially labeled arbitrarily, and they have to be relabeled with a classical compass sense of direction. We first describe an algorithm where the relabeling of the edges is performed by a mobile agent that carries a token. The algorithm is optimal both in terms of number of tokens (with no tokens the task cannot be performed), and in terms of number of moves. We then show that the same technique can be used to orient the torus in the classical message-passing environment, thus obtaining an orientation algorithm that improves all the existing ones in this setting. [ABSTRACT FROM AUTHOR]

In this paper we consider a network where an intruder is moving "contaminating" the nodes it passes by, and we focus on the problem of decontaminating such a network by a team of mobile agents. The contamination/decontamination process has the following asynchronous dynamics: when the team is deployed all nodes are assumed to be contaminated, when an agent transits on a node, it will clean the node, when the node is left with no agent, the node will be recontaminated as soon as at least one of its neighbours is contaminated. We study the problem in asynchronous chordal ring networks and in tori. We consider two variations of the model: one where agents have only local knowledge, the other in which they have "visibility", i.e., they can "see" the state of their neighbouring nodes. We first derive lower bounds on the minimum number of agents necessary for the decontamination. In the case of chordal rings we show that the number of agents necessary to perform the cleaning does not depend on the size of the network; in fact it is linear in the length of the longest chord (provided that it is not too long). In the case of a torus, the minimum number of agents is equal to 2 · h, where h is the smallest dimension. We then propose optimal strategies for decontamination and we analyse the number of moves and the time complexity of the decontamination algorithms, showing that the visibility assumption allows us to decrease substantially both complexity measures. Another advantage of the "visibility model" is that agents move independently and autonomously without requiring any coordination. [ABSTRACT FROM AUTHOR]

To generate a proper Korean predicate, a natural modal expression is the most important factor for a machine translation (MT) system. Tense, aspect, mood, negation, and voice are the major constituents related to modal expression. The linguistic encoding of a modal expression is quite different between Chinese and Korean in terms of linguistic typology and genealogy. In this paper, a new applicable categorization of Korean modality system viz. tense, aspect, mood, negation, and voice, will be proposed through a contrastive analysis of Chinese and Korean from the viewpoint of a practical MT system. In order to precisely determine the modal expression, effective feature selection frameworks for Chinese are presented with a variety of machine learning methods. As a result, our proposed approach achieved an accuracy of 83.10%. [ABSTRACT FROM AUTHOR]

We consider the following online scheduling problem. We are given a set of jobs, each having an integral release time and deadline, unit processing length, and a nonnegative real weight. In each time unit one job is to be scheduled, and the objective is to maximize the total value (weight) obtained by scheduling the jobs. This problem arises in the scheduling of packets in network switches supporting quality-of-service (QoS). Previous algorithms for this problem are 2-competitive. in this paper we propose a new algorithm that achieves an improved competitive ratio when the importance ratio is bounded. Specifically, for job weights within the range [1..B], our algorithm is 2 - 1/([lg B] + 2)-competitive, and the bound is tight. [ABSTRACT FROM AUTHOR]

Fisher Linear Discriminant Analysis (LDA) has been successfully used as a data discriminantion technique for face recognition. This paper has developed a novel subspace approach in determining the optimal projection. This algorithm effectively solves the small sample size problem and eliminates the possibility of losing discriminative information. Through the theoretical derivation, we compared our method with the typical PCA-based LDA methods, and also showed the relationship between our new method and perturbation-based method. The feasibility of the new algorithm has been demonstrated by comprehensive evaluation and comparison experiments with existing LDA-based methods. [ABSTRACT FROM AUTHOR]

The interest for multimedia contents authentication has recently increased. In particular watermarking-based authentication schemes seem to be offering some advantages with respect to classical cryptography tools (e.g. real content authentication, localization of manipulations, storage format independence, transparency to common signal processing, etc.). In this paper a simple and secure self recovery authentication algorithm which hides an image digest into some DWT subbands of the to be authenticated image is presented. This technique has been designed for video surveillance and/or remote sensing applications. The main goal of this approach is to detect possible malevolent object manipulations undergone by the image (object replacing and/or deletion) by means of a self recovery processing. This valuable characteristic has to be maintained also when an image is processed through an usual and friendly transformation like JPEG compression. Particular care is given to make the scheme robust against innocuous manipulations, and secure against forgery attempts. Experimental results are presented that demonstrate the good performance of the proposed system. [ABSTRACT FROM AUTHOR]

The subtree transfer (STT) distance is one of the distance metric for comparing phylogenies. Previous work on computing the STT distance considered degree-3 trees only. In this paper, we give an approximation algorithm for the STT distance for degree-d trees with arbitrary d and with generalized STT operations. Also, some NP-hardness results related to STT distance are presented. [ABSTRACT FROM AUTHOR]

A polygonal approximation captures the essential features of a digital planar curve and yields a compact representation. Those points of the digital curve that carry vital information about the shape of the curve form the vertices of the approximating polygon and are called significant vertices. In this paper, we present a genetic algorithm-based approach to locate a specified number of significant points, such that the approximation error between the original curve and its polygonal version obtained by joining the adjacent significant points is minimized. By using a priori knowledge about the shape of the curve we confine our search to only those points of the curve that have the potential of qualifying as significant points. We also incorporate chromosome differentiation to improve upon the effectiveness of the search in arriving at a near-optimal polygonal approximation. Finally, we show that the proposed method performs remarkably well when evaluated in terms of the metrics available for assessing the goodness of a polygonal approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present a new approach to geometrical modeling which allows the user to easily characterize and control the shape defined to a closed surface. We will focus on dealing with the shape's topological, morphological and geometrical properties separately. To do this, we have based our work on the following observations concerning surfaces defined by control-points, and implicit surfaces with skeleton. They both provide complementary approaches to the surface's deformation, and both have specific advantages and limits. We thus attempted to conceive a model which integrates the local and geometrical characterization induced by the control points, as well as the representation of the morphology given by the skeleton. Knowing that the lattice of control points is close to the surface and that the skeleton is centered in the related shape, we thought of a 3-layer model. The transition layer separates the local geometrical considerations from those linked to the global morphology. We apply our model to shape design in order to modify an object in an interactive and ergonomic way, as well as to reconstruction which allows better shape understanding. To do so, we present the algorithms related to these processes. [ABSTRACT FROM AUTHOR]

This research addresses scheduling issues in networked computer systems with survivability requirements, i.e. systems in which essential services must survive malicious acts. In order to achieve survivability based on spatial redundancy, agreement algorithms are needed as a mechanism to consolidate results of individual replicas. The potentially enormous overhead associated with communication and voting schemes of the algorithms put unique burdens on the scheduler as the efficiency of scheduling determines the suitability of the agreement algorithm. This paper derives agreement task graphs, representing computations, and inter-process communication based on phantom tasks. Task graph primitives are identified and it is shown how their scheduling directly influences the performance of the agreement algorithm. Finally, the notion of dynamic k-of-N precedence is introduced and its impact on resource reclaiming for early stopping algorithms is discussed. [ABSTRACT FROM AUTHOR]

Most of the FPGA's area and delay are due to routing. Considering routability at earlier steps of the CAD flow would both yield better quality and faster design process. In this paper, we discuss the metrics that affect routability in packing logic into clusters. We are presenting a routability-driven clustering method for cluster-based FPGAs. Our method packs LUTs into logic clusters while incorporating routability metrics into a cost function. Based on our routability model, the routability in timing-driven packing algorithm is analyzed. We integrate our routability model into a timing-driven packing algorithm. Our method yields up to 50% improvement in terms of the minimum number of routing tracks compared to VPack (16.5% on average). The average routing area improvement is 27% over VPack and 12% over t-VPack. [ABSTRACT FROM AUTHOR]

This paper presents a fast Neural Network algorithm, in which the step is regarded as the function of the error and the output function of network node, and weight is calculated by different step. By adopting the fast NN algorithm, we developed a speaker-independent speech recognition system. The experiment shows that the new algorithm is over 10 times faster than the traditional BP algorithm and has better performance and spreading ability. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of constructing a multicast tree in star interconnection networks under the single-port communication model. Unlike previous schemes for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme of [formula] time units for the star graph of dimension n. [ABSTRACT FROM AUTHOR]

In 1992, a new spatial temporal computing idea had been proposed, the CNN Universal Machine. It turned out that a new paradigm in computing on image flows, a Universal Machine on Flows, has ignited the intellect of hundreds of researchers. Today, visual microprocessors based on this idea can perform about TeraOPS computing power and 10 000 frames per second. In this paper, after a brief description of the history of the invention, architectural advances, physical implementation, algorithmic developments, as well as the biology relevance, theoretical aspects, mission critical applications, and new directions are reviewed. [ABSTRACT FROM AUTHOR]

In this paper we discuss efficient symbolic representations for infinite-state systems specified using linear arithmetic constraints. We give algorithms for constructing finite automata which represent integer sets that satisfy linear constraints. These automata can represent either signed or unsigned integers and have a lower number of states compared to other similar approaches. We present efficient storage techniques for the transition function of the automata and extend the construction algorithms to formulas on both boolean and integer variables. We also derive conditions which guarantee that the pre-condition computations used in symbolic verification algorithms do not cause an exponential increase in the automata size. We experimentally compare different symbolic representations by using them to verify non-trivial concurrent systems. Experimental results show that the symbolic representations based on our construction algorithms outperform the polyhedral representation used in Omega Library, and the automata representation used in LASH. [ABSTRACT FROM AUTHOR]

Hybrid dynamic systems include both continuous and discrete state variables. Properties of hybrid systems, which have an infinite state space, can often be verified using ordinary model checking together with a finite-state abstraction. Model checking can be inconclusive, however, in which case the abstraction must be refined. This paper presents a new procedure to perform this refinement operation for abstractions of hybrid systems. Following an approach originally developed for finite-state systems [11, 25], the refinement procedure constructs a new abstraction that eliminates a counterexample generated by the model checker. For hybrid systems, analysis of the counterexample requires the computation of sets of reachable states in the continuous state space. We show how such reachability computations with varying degrees of complexity can be used to refine hybrid system abstractions efficiently. Examples illustrate our counterexample-guided refinement procedure. Experimental results for a prototype implementation indicate significant advantages over existing methods. [ABSTRACT FROM AUTHOR]

Please send your abstracts (or copies of papers that you want to see reviewed here) to vladik@utep.edu, or by regular mail to Vladik Kreinovich, Department of Computer Science, University of Texas at El Paso, El Paso, TX 79968, USA. [ABSTRACT FROM AUTHOR]

This section is maintained by Vladik Kreinovich. Please send your abstracts (or copies of papers that you want to see reviewed here) to vladik@cs.utep.edu, or by regular mail to: Vladik Kreinovich, Department of Computer Science, University of Texas at El Paso, El Paso, TX 79968, USA. [ABSTRACT FROM AUTHOR]