An efficient algorithm for Pawlak reduction based on simplified discernibility matrix

Since the definition of attribute reduction based on classic discernibility matrix differs from that of it based on positive region, a new simplified discernibility matrix and the corresponding definition of attribute reduction were proposed. At the same time, it proves that the proposed definition is identical to its definition based on positive region. For computing simplified discernibility matrix, the indiscernibility relation, which is also called equivalence relation, should usually be calculated at first, so a new algorithm for computing equivalence relation was designed with radix sorting, whose temporal complexity is O(|C||U|). Furthermore, an efficient attribute reduction algorithm is proposed, whose temporal complexity and spatial complexity are cut down to max(O(|C|²|U′ _pos ||U′|,O(|U||C|)) and max(O(|C||U′ _pos ||U′|,O(|U|)) respectively. At last, an example is used to illustrate efficiency of the new algorithms.     

Directed Graph Pattern Matching and Topological Embedding

Pattern matching in directed graphs is a natural extension of pattern matching in trees and has many applications to different areas. In this paper, we study several pattern matching problems in ordered labeled directed graphs. For the rooted directed graph pattern matching problem, we present an efficient algorithm which, given a pattern graphPand a target graphT, runs in time and spaceO(|E_P| |V_T| + |E_T|). It is faster than the best known method by a factor ofmin{|E_T|, |E_P| |V_T|}. This algorithm can also solve the directed graph pattern matching problem without increasing time or space complexity. Our solution to this problem outperforms the best existing method by Katzenelson, Pinter and Schenfeld by a factor ofmin{|V_P| |E_T|, |V_P| |E_P| |V_T|}. We also present an algorithm for the directed graph topological embedding problem which runs in timeO(|V_P| |E_T| + |E_P|) and spaceO(|V_P| |V_T| + |E_P| + |E_T|). To our knowledge, this algorithm is the first one for this problem.     

Uniform bound in the central limit theorem for Banach space valued dependent random variables

Let F be a Banach space with a sufficiently smooth norm. Let (X_i)_i≤n be a sequence in L_F², and T be a Gaussian random variable T which has the same covariance as X = Σ_i≤nX_i. Assume that there exists a constant G such that for s, δ≥0, we have P(sTs+δ)Gδ. (*) We then give explicit bounds of Δ(X) = sup_i|P(|X|≤t)−P(|T|≤t)| in terms of truncated moments of the variables X_i. These bounds hold under rather mild weak dependence conditions of the variables. We also construct a Gaussian random variable that violates (^*).     

Counting points in hypercubes and convolution measure algebras

It is shown that ifA andB are non-empty subsets of {0, 1} ⁿ (for somenεN) then |A+B|≧(|A||B|)^α where α=(1/2) log₂ 3 here and in what follows. In particular if |A|=2 ^n-1 then |A+A|≧3 ^n-1 which anwers a question of Brown and Moran. It is also shown that if |A| = 2 ^n-1 then |A+A|=3 ^n-1 if and only if the points ofA lie on a hyperplane inn-dimensions. Necessary and sufficient conditions are also given for |A +B|=(|A||B|)^α. The above results imply the following improvement of a result of Talagrand [7]: ifX andY are compact subsets ofK (the Cantor set) withm(X),m(Y)>0 then λ(X+Y)≧2(m(X)m(Y))^α wherem is the usual measure onK and λ is Lebesgue measure. This also answers a question of Moran (in more precise terms) showing thatm is not concentrated on any proper Raikov system.     

New Algorithm for Ordered Tree-to-Tree Correction Problem

The ordered tree-to-tree correction problem is to compute the minimum edit cost of transforming one ordered tree to another one. This paper presents a new algorithm for this problem. Given two ordered trees S and T, our algorithm runs in O(|S| |T| + min { ²_S|T| + ^2.5_{S T}, ²_T|S| + ^2.5_{T S}) time, where _S denotes the number of leaves of S and _S denotes the depth of S. The previous best algorithms for this problem run in O(|S| |T| min { _S, _S} min { _T, _T}) time (K. Zhang and D. Shasha, SIAM J. Comput.18, No. 6 (1989), 1245–1262) and in O(min {|S|²|T| log₂ |T|, |T|²|S| log₂ |S|}) time (P. N. Klein, in “Algorithms—ESA'98, 6th Annual European Symposium” (G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci, Eds.), Lecture Notes in Computer Science, Vol. 1461, pp. 91–102, Springer-Verlag, Berlin/New York, 1998). As a comparison, our algorithm is asymptotically faster for certain kind of trees.     

On Suboptimal LCS-alignments for Independent Bernoulli Sequences with Asymmetric Distributions

Let X = X ₁ ... X _n and Y = Y ₁ ... Y _n be two binary sequences with length n. A common subsequence of X and Y is any subsequence of X that at the same time is a subsequence of Y; The common subsequence with maximal length is called the longest common subsequence (LCS) of X and Y. LCS is a common tool for measuring the closeness of X and Y. In this note, we consider the case when X and Y are both i.i.d. Bernoulli sequences with the parameters ϵ and 1 − ϵ, respectively. Hence, typically the sequences consist of large and short blocks of different colors. This gives an idea to the so-called block-by-block alignment, where the short blocks in one sequence are matched to the long blocks of the same color in another sequence. Such and alignment is not necessarily a LCS, but it is computationally easy to obtain and, therefore, of practical interest. We investigate the asymptotical properties of several block-by-block type of alignments. The paper ends with the simulation study, where the of block-by-block type of alignments are compared with the LCS.     

Global existence and L ∞ estimates of solutions for a quasilinear parabolic system

In this paper, we study the global existence, L^∞ estimates and decay estimates of solutions for the quasilinear parabolic system u_t = div (|∇ u|^m ∇ u) + f(u, v), v_t = div (|∇ v|^m ∇ v) + g(u,v) with zero Dirichlet boundary condition in a bounded domain Ω ⊂ R^N. In particular, we find a critical value for the existence and nonexistence of global solutions to the equation u_t = div (|∇ u|^m ∇ u) + λ |u|^{α - 1} u.     

Visibility queries in a polygonal region

In this paper, we consider the problem of computing the region visible to a query point located in a given polygonal domain. The polygonal domain is specified by a simple polygon with m holes and a total of n vertices. We provide two bounds on the complexity of this problem. One approach constructs a data structure with space complexity O(n²) in time O(n²lgn) and yields a query time of O((1+min(m,|V(q)|))lg²n+m+|V(q)|). Here, V(q) represents the set of vertices of the visibility polygon of a query point q, and |E| denotes the number of edges in the visibility graph. The other approach provides a data structure with space complexity O(min(|E|,mn)+n) in time O(T+|E|+nlgn) with the query time of O(|V(q)|lgn+m). Here, T is the time to triangulate the given polygonal region (which is O(n+mlg¹⁺m) for a small positive constant >0). In both of these approaches, O(m) additive factor in the query time is eliminated with an additional O((min(|E|,mn))²) space and an additional O(m(min(|E|,mn))²) preprocessing time.     

Bahadur representation of nonparametric M-estimators for spatial processes

Under some mild conditions, we establish a strong Bahadur representation of a general class of nonparametric local linear M-estimators for mixing processes on a random field. If the socalled optimal bandwidth hn = O（｜n｜^-1/5）, n ∈ Z^d, is chosen, then the remainder rates in the Bahadur representation for the local M-estimators of the regression function and its derivative are of order O（｜n｜^-4/5 log ｜n｜）. Moreover, we derive some asymptotic properties for the nonparametric local linear M-estimators as applications of our result.     

Dynamic Text Indexing under String Updates

This paper generalizes the dynamic text indexing problem, introduced in [15], to insertion and deletion of strings. The problem is to quickly answer on-line queries about the occurrences of arbitrary pattern strings in a text that may change due to insertion or deletion of strings from it. To treat strings as atomic objects, we provide new sequential techniques and related data structures, which combine the suffix tree with the naming technique used in parallel computation on strings. We also introduce a geometric interpretation of the problem of finding the occurrences of a pattern in a given substring of the text. As a result, the algorithm allows the insertion in the text of a stringSinO(|S| log(n + |S|)) amortized time, and the deletion from the text of a stringSinO(|S| log n) amortized time, wherenis the length of the current text. A pattern search requiresO(p log p + upd ( + log p) + pocc) worst-case time, wherepis the length of the pattern andpoccis the number of its occurrences in the current text, obtained after the execution ofupdupdate operations. This solution requiresO(n² log n) space, which is not initialized.We also provide a technique to reduce the space toO(n log n), yielding a solution that requiresO((p + upd) log p + pocc) query time in the worst-case,O(|S| log^3/2(|S| + n)) amortized time to insert a stringSin, andO(|S| log^3/2n) amortized time to delete a stringSfrom the current text.Furthermore, we use our techniques to solve the novel on-line dynamic tree matching problem that requires the on-line detection of the occurrences of an arbitrary subtree in a forest of ordered labeled trees. The forest may change due to insertion or deletion of subtrees or by renaming of some nodes. Such a problem is solved by a simple reduction to the dynamic text indexing problem.     

Level crossing probabilities I: One-dimensional random walks and symmetrization

We prove for an arbitrary random walk in R¹ with independent increments that the probability of crossing a level at a given time n is O(n−1/2). Moment or symmetry assumptions are not necessary. In removing symmetry the (sharp) inequality P(|X+Y|?1)<2P(|X−Y|?1) for independent identically distributed X,Y is used. In part II we shall discuss the connection of this result to ‘polygonal recurrence’ of higher-dimensional walks and some conjectures on directionally reinforced random walks in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239-252. [5]].     

Decremental Dynamic Connectivity

We consider Las Vegas randomized dynamic algorithms for on-line connectivity problems with deletions only. In particular, we show that starting from a graph with m edges and n nodes, we can maintain a spanning forest during m deletions in O(m log(n²/m) + n(log n)³(log log n)²) expected time, which is O(m) if m = Θ(n²) and O(m log n) if m = Ω(n(log n log log n)²). The deletions may be interspersed with connectivity queries, each of which is answered in constant time. The previous best bound was O(m log² n) by Henzinger and Thorup which covered both insertions and deletions. The result is based on a general randomized reduction for edge connectivity problems of many deletions-only queries to a few deletions and insertions queries. For 2-edge connectivity, the complexity is improved from O(m(log n)⁵) to O(m log(n²/m) + n(log n)⁶(log log n)²). For the general decremental k-edge-connectivity problem, we get a total running time of O(k²n² polylog n). Here the previous best bound was O(kmn polylog n). Improved running times are also achieved for the static consensus tree problem, with applications to computational biology and relational data bases.     

On the minimum of harmonic functions

Letu be a function harmonic in the unit disc or in the plane, and letu(z)≤M(|z|) for a majorantM. We formulate conditions onM that guarantee thatu(z)≥−(1+o(1))M(|z|) for |z|→1 in the disc and for |z|→∞ in the plane.     

Exponential bounds of mean error for the kernel estimates of regression functions

Let (X, Y), (X₁, Y₁), …, (X_n, Y_n) be i.d.d. R^r × R-valued random vectors with E|Y| < ∞, and let Q_n(x) be a kernel estimate of the regression function Q(x) = E(Y|X = x). In this paper, we establish an exponential bound of the mean deviation between Q_n(x) and Q(x) given the training sample Zⁿ = (X₁, Y₁, …, X_n, Y_n), under conditions as weak as possible.     

Consistency of a recursive nearest neighbor regression function estimate

Let (X, Y) be an ^d × -valued random vector and let (X₁, Y₁),…,(X_N, Y_N) be a random sample drawn from its distribution. Divide the data sequence into disjoint blocks of length l₁, …, l_n, find the nearest neighbor to X in each block and call the corresponding couple (X_i^*, Y_i^*). It is shown that the estimate m_n(X) = Σ_{i = 1}ⁿ w_niY_i^*/Σ_{i = 1}ⁿ w_ni of m(X) = E{Y|X} satisfies E{|m_n(X) − m(X)|^p} 0 (p ≥ 1) whenever E{|Y|^p} < ∞, l_n ∞, and the triangular array of positive weights {w_ni} satisfies sup_{i ≤ n}w_ni/Σ_{i = 1}ⁿ w_ni 0. No other restrictions are put on the distribution of (X, Y). Also, some distribution-free results for the strong convergence of E{|m_n(X) − m(X)|^p|X₁, Y₁,…, X_N, Y_N} to zero are included. Finally, an application to the discrimination problem is considered, and a discrimination rule is exhibited and shown to be strongly Bayes risk consistent for all distributions.     

An exact algorithm for solving the vertex separator problem

Given G = (V, E) a connected undirected graph and a positive integer β(|V|), the vertex separator problem is to find a partition of V into no-empty three classes A, B, C such that there is no edge between A and B, max{|A|, |B|} ≤ β(|V|) and |C| is minimum. In this paper we consider the vertex separator problem from a polyhedral point of view. We introduce new classes of valid inequalities for the associated polyhedron. Using a natural lower bound for the optimal solution, we present successful computational experiments.     

Some solutions for the spin glass system and for systems originating from it

For the spin glass system the solutions, u = νΦ and u = νx/|x| are considered, where ν is a scalar function and Φε?³ is constant. For a system originating from the spin glass one, a solution u = tan[q(|x|/t)]x/|x| is considered.     

Second-order linearity of the general signed-rank statistic

Let X₁,…, X_n be i.i.d. random variables symmetric about zero. Let R_i(t) be the rank of |X_i − tn^−1/2| among |X₁ − tn^−1/2|,…, |X_n − tn^−1/2| and T_n(t) = Σ_{i = 1}ⁿφ((n + 1)⁻¹R_i(t))sign(X_i − tn^−1/2). We show that there exists a sequence of random variables V_n such that sup_{0 ≤ t ≤ 1} |T_n(t) − T_n(0) − tV_n| → 0 in probability, as n → ∞. V_n is asymptotically normal.     

Minimal Extensions in Tensor Product Spaces

LetX,Ybe two separable Banach spaces and letVXandWYbe finite dimensional subspaces. Suppose thatVSX,WZYand letM (S, V),N (Z, W). We will prove that ifαis a reasonable, uniform crossnorm onXYthenλ_MN(V_αW,X_αY)=λ_M(V, X) λ_N(W, Y).Here for any Banach spaceX,VSXandM (S, V)

Full-size image

Also some applications of the above mentioned result will be presented.     

Optimal mappings with minimum number of connected components in tree-to-tree comparison problems

In this paper we consider the problem of finding a minimum cost mapping between two unordered trees which induces a graph with a minimum number of connected components. The proposed algorithm is based on the generalization of an algorithm for computing an edit distance between trees, and it solves the stated problem in sequential time precisely in O(|T₁|×|T₂|×(degT₁+degT₂)×log₂(degT₁+degT₂)).