Negative selection algorithms on strings with efficient training and linear-time classification

A string-based negative selection algorithm is an immune-inspired classifier that infers a partitioning of a string space Σ^? into “normal” and “anomalous” partitions from a training set S containing only samples from the “normal” partition. The algorithm generates a set of patterns, called “detectors”, to cover regions of the string space containing none of the training samples. Strings that match at least one of these detectors are then classified as “anomalous”. A major problem with existing implementations of this approach is that the detector generating step needs exponential time in the worst case. Here we show that for the two most widely used kinds of detectors, the r-chunk and r-contiguous detectors based on partial matching to substrings of length r, negative selection can be implemented more efficiently by avoiding generating detectors altogether: for each detector type, training set S⊆Σ^? and parameter r≤? one can construct an automaton whose acceptance behaviour is equivalent to the algorithm’s classification outcome. The resulting runtime is O(|S|?r|Σ|) for constructing the automaton in the training phase and O(?) for classifying a string.     

On the hardness of finding near-optimal multicuts in directed acyclic graphs

Given an edge-weighted (di)graph and a list of source-sink pairs of vertices of this graph, the minimum multicut problem consists in selecting a minimum-weight set of edges (or arcs), whose removal leaves no path from each source to the corresponding sink. This is a well-known NP-hard problem, and improving several previous results, we show that it remains APX-hard in unweighted directed acyclic graphs (DAG), even with only two source-sink pairs. This is also true if we remove vertices instead of arcs.     

On using prototype reduction schemes to enhance the computation of volume-based inter-class overlap measures

In most pattern recognition (PR) applications, it is advantageous if the accuracy (or error rate) of the classifier can be evaluated or bounded prior to testing it in a real-life setting. It is also well known that if the two class-conditional distributions have a large overlapping volume (almost all the available work on “overlapping of classes” deals with the case when there are only two classes), the classification accuracy is poor. This is because if we intend to use the classification accuracy as a criterion for evaluating a PR system, the points within the overlapping volume tend to lead to maximal misclassification. Unfortunately, the computation of the indices which quantify the overlapping volume is expensive. In this vein, we propose a strategy of using a prototype reduction scheme (PRS) to approximately, but quickly, compute the latter. In this paper, we demonstrate, first of all, that this is an extremely expedient proposition. Indeed, we show that by completely discarding (we are not aware of any reported scheme which discards “irrelevant” sample (training) points, and which simultaneously attains to an almost-comparable accuracy) the points not included by the PRS, we can obtain a reduced set of sample points, using which, in turn, the measures for the overlapping volume can be computed. The value of the corresponding figures is comparable to those obtained with the original training set (i.e., the one which considers all the data points) even though the computations required to obtain the prototypes and the corresponding measures are significantly less. The proposed method has been rigorously tested on artificial and real-life datasets, and the results obtained are, in our opinion, quite impressive—sometimes faster by two orders of magnitude.     

A necessary and sufficient condition for parameter insensitive disturbance-rejection problem with state feedback

In this paper a necessary and sufficient condition for a parameter insensitive disturbance-rejection problem with state feedback which was pointed out as an open problem by Bhattacharyya to be solvable is proved. A constructive algorithm of simultaneously (A,B)-invariant subspaces for a finite-number of linear systems and a relationship between simultaneously (A,B)-invariant subspaces and generalized (A,B)-invariant subspaces play an important role to prove the main result.     

On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

Distinct squares in run-length encoded strings

Squares are strings of the form ww where w is any nonempty string. Two squares ww and w^′w^′ are of different types if and only if w≠w^′. Fraenkel and Simpson [Avieri S. Fraenkel, Jamie Simpson, How many squares can a string contain? Journal of Combinatorial Theory, Series A 82 (1998) 112-120] proved that the number of square types contained in a string of length n is bounded by O(n). The set of all different square types contained in a string is called the vocabulary of the string. If a square can be obtained by a series of successive right-rotations from another square, then we say the latter covers the former. A square is called a c-square if no square with a smaller index can cover it and it is not a trivial square. The set containing all c-squares is called the covering set. Note that every string has a unique covering set. Furthermore, the vocabulary of the covering set are called c-vocabulary. In this paper, we prove that the cardinality of c-vocabulary in a string is less than , where N is the number of runs in this string.     

On cool congruence formats for weak bisimulations

In TCS 146, Bard Bloom presented rule formats for four main notions of bisimulation with silent moves. He proved that weak bisimulation equivalence is a congruence for any process algebra defined by WB cool rules, and established similar results for rooted weak bisimulation (Milner’s “observational congruence”), branching bisimulation and rooted branching bisimulation. This study reformulates Bloom’s results in a more accessible form and contributes analogues for (rooted) η-bisimulation and (rooted) delay bisimulation. Moreover, finite equational axiomatisations of rooted weak bisimulation equivalence are provided that are sound and complete for finite processes in any RWB cool process algebra. These require the introduction of auxiliary operators with lookahead, and an extension of Bloom’s formats for this type of operator with lookahead. Finally, a challenge is presented for which Bloom’s formats fall short and further improvement is called for.     

Group path covering and distance two labeling of graphs

For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)−f(v)|?d if uv∈E(G), and |f(u)−f(v)|?1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f. The L(d,1)-labeling number of G, denoted by λd,1(G), is the minimum span over all L(d,1)-labelings of G. An L^′(d,1)-labeling of a graph G is an L(d,1)-labeling of G which assigns different labels to different vertices. Denote by the L^′(d,1)-labeling number of G. Georges et al. [Discrete Math. 135 (1994) 103-111] established relationship between the L(2,1)-labeling number of a graph G and the path covering number of Gc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t-group path covering. Then we establish the relationship between the L^′(d,1)-labeling number of a graph G and the (d−1)-group path covering number of Gc. Using this result, we prove that and for bipartite graphs G can be computed in polynomial time.     

Super connectivity of line graphs

The super connectivity κ^′ and the super edge-connectivity λ^′ are more refined network reliability indices than connectivity κ and edge-connectivity λ. This paper shows that for a connected graph G with order at least four rather than a star and its line graph L(G), κ^′(L(G))=λ^′(G) if and only if G is not super-λ^′. As a consequence, we obtain the result of Hellwig et al. [Note on the connectivity of line graphs, Inform. Process. Lett. 91 (2004) 7] that κ(L(G))=λ^′(G). Furthermore, the authors show that the line graph of a super-λ^′ graph is super-λ if the minimum degree is at least three.     

Hierarchical trajectory refinement for a class of nonlinear systems

Trajectory generation for nonlinear control systems is an important and difficult problem. In this paper, we provide a constructive method for hierarchical trajectory refinement. The approach is based on the recent notion of φ-related control systems. Given a control affine system satisfying certain assumptions, we construct a φ-related control system of smaller dimension. Trajectories designed for the smaller, abstracted system are guaranteed, by construction, to be feasible for the original system. Constructive procedures are provided for refining trajectories from the coarser to the more detailed system.     

A new framework for identifying differentially expressed genes

Microarrays have been widely used to classify cancer samples and discover the biological types, for example tumor versus normal phenotypes in cancer research. One of the challenging scientific tasks in the post-genomic epoch is how to identify a subset of differentially expressed genes from thousands of genes in microarray data which will enable us to understand the underlying molecular mechanisms of diseases, accurately diagnosing diseases and identifying novel therapeutic targets. In this paper, we propose a new framework for identifying differentially expressed genes. In the proposed framework, genes are ranked according to their residuals. The performance of the framework is assessed through applying it to several public microarray data. Experimental results show that the proposed method gives more robust and accurate rank than other statistical test methods, such as t-test, Wilcoxon rank sum test and KS-test. Another novelty of the method is that we design an algorithm for selecting a small subset of genes that show significant variation in expression (“outlier” genes). The number of genes in the small subset can be controlled via an alterable window of confidence level. In addition, the results of the proposed method can be visualized. By observing the residual plot, we can easily find genes that show significant variation in two groups of samples and learn the degrees of differential expression of genes. Through a comparison study, we found several “outlier” genes which had been verified in previous biological experiments while they were either not identified by other methods or had lower ranks in standard statistical tests.     

Stability properties of reset systems

Stability properties for a class of reset systems, such as systems containing a Clegg integrator, are investigated. We present Lyapunov based results for verifying L₂ and exponential stability of reset systems. Our results generalize the available results in the literature and can be easily modified to cover L_p stability for arbitrary p∈[1,∞]. Several examples illustrate that introducing resets in a linear system may reduce the L₂ gain if the reset controller parameters are carefully tuned.     

A note on soft topological spaces

Shabir and Naz (2011) [12] introduced and studied the notions of soft topological spaces, soft interior, soft closure and soft separation axioms. But we found that some results are incorrect (see their Remark 3.23). So the purpose of this note is, first, to point out some errors in Remark 4 and Example 9 of Shabir and Naz (2011) [12], and second, to investigate properties of soft separation axioms defined in Shabir and Naz (2011) [12]. In particular, we investigate the soft regular spaces and some properties of them. We show that if a soft topological space (X,τ,E) is soft T₁ and soft regular (i.e. a soft T₃-space), then (x,E) is soft closed for each x∈X (their Theorem 3.21).     

State feedback control of continuous-time T-S fuzzy systems via switched fuzzy controllers

This paper studies the problem of state feedback control of continuous-time T-S fuzzy systems. Switched fuzzy controllers are exploited in the control design, which are switched based on the values of membership functions, and the control scheme is an extension of the parallel distributed compensation (PDC) scheme. Sufficient conditions for designing switched state feedback controllers are obtained with meeting an H_∞ norm bound requirement and quadratic D stability constraints. It is shown that the new control design method provides less conservative results than the corresponding ones via the parallel distributed compensation (PDC) scheme. A numerical example is given to illustrate the effectiveness of the proposed method.     

Super restricted edge connected Cartesian product graphs

An edge-cut F of a connected graph G is called a restricted edge-cut if G−F contains no isolated vertices. The minimum cardinality of all restricted edge-cuts is called the restricted edge-connectivity λ^′(G) of G. A graph G is said to be λ^′-optimal if λ^′(G)=ξ(G), where ξ(G) is the minimum edge-degree of G. A graph is said to be super-λ^′ if every minimum restricted edge-cut isolates an edge. This article gives a sufficient condition for Cartesian product graphs to be super-λ^′. Using this result, certain classes of networks which are recursively defined by the Cartesian product can be simply shown to be super-λ^′.     

Online computation with advice

We consider a model for online computation in which the online algorithm receives, together with each request, some information regarding the future, referred to as advice. The advice is a function, defined by the online algorithm, of the whole request sequence. The advice provided to the online algorithm may allow an improvement in its performance, compared to the classical model of complete lack of information regarding the future. We are interested in the impact of such advice on the competitive ratio, and in particular, in the relation between the size b of the advice, measured in terms of bits of information per request, and the (improved) competitive ratio. Since b=0 corresponds to the classical online model, and b=⌈log∣A∣⌉, where A is the algorithm’s action space, corresponds to the optimal (offline) one, our model spans a spectrum of settings ranging from classical online algorithms to offline ones.In this paper we propose the above model and illustrate its applicability by considering two of the most extensively studied online problems, namely, metrical task systems (MTS) and the k-server problem. For MTS we establish tight (up to constant factors) upper and lower bounds on the competitive ratio of deterministic and randomized online algorithms with advice for any choice of 1≤b≤Θ(logn), where n is the number of states in the system: we prove that any randomized online algorithm for MTS has competitive ratio Ω(log(n)/b) and we present a deterministic online algorithm for MTS with competitive ratio O(log(n)/b). For the k-server problem we construct a deterministic online algorithm for general metric spaces with competitive ratio k^O(1/b) for any choice of Θ(1)≤b≤logk.     

Computation, approximation and stability of explicit feedback min-max nonlinear model predictive control

This paper presents an approximate multi-parametric Nonlinear Programming (mp-NLP) approach to explicit solution of feedback min-max NMPC problems for constrained nonlinear systems in the presence of bounded disturbances and/or parameter uncertainties. It is based on an orthogonal search tree structure of the state space partition and consists in constructing a piecewise nonlinear (PWNL) approximation to the optimal sequence of feedback control policies. Conditions guaranteeing the robust stability of the closed-loop system in terms of a finite l₂-gain are derived.