FreeS: A fast algorithm to discover frequent free subtrees using a novel canonical form

Web data can often be represented in free tree form; however, free tree mining methods seldom exist. In this paper, a computationally fast algorithm FreeS is presented to discover all frequently occurring free subtrees in a database of labelled free trees. FreeS is designed using an optimal canonical form, BOCF that can uniquely represent free trees even during the presence of isomorphism. To avoid enumeration of false positive candidates, it utilises the enumeration approach based on a tree-structure guided scheme. This paper presents lemmas that introduce conditions to conform the generation of free tree candidates during enumeration. Empirical study using both real and synthetic datasets shows that FreeS is scalable and significantly outperforms (i.e. few orders of magnitude faster than) the state-of-the-art frequent free tree mining algorithms, HybridTreeMiner and FreeTreeMiner.

The Jordan canonical form for a class of weighted directed graphs

Recently, Cardon and Tuckfield (2011) [1] have described the Jordan canonical form for a class of zero-one matrices, in terms of its associated directed graph. In this paper, we generalize this result to describe the Jordan canonical form of a weighted adjacency matrix A in terms of its weighted directed graph.

A canonical form for nonderogatory matrices under unitary similarity

A square matrix is nonderogatory if its Jordan blocks have distinct eigenvalues. We give canonical forms for (1) nonderogatory complex matrices up to unitary similarity, and (2) pairs of complex matrices up to similarity, in which one matrix has distinct eigenvalues. The types of these canonical forms are given by undirected and, respectively, directed graphs with no undirected cycles. (C) 2011 Elsevier Inc. All rights reserved.

A simple demonstration of the existence of the jordan canonical form for any square matrix

All the demonstrations known to this author of the existence of the Jordan Canonical Form are somewhat complex - usually invoking the use of new spaces, and what not. These demonstrations are usually too difficult for an average Mathematics student to understand how he or she can obtain the Jordan Canonical Form for any square matrix. The method here proposed not only demonstrates the existence of such forms but, additionally, shows how to find them in a step by step manner. I do not claim that the following demonstration is in any way “elegant” (by the standards of elegance in fashion nowadays among mathematicians) but merely simple (undergraduate students taking a fist course in Matrix Algebra would understand how it works).

Constructing a Canonical form of a Matrix in Several Problems about Combinatorial Designs

Partially supported by the Bulgarian Science Fund contract with TU Varna, No 487.

Reed-Muller Canonical Forms in Multivalued Logic

Canonical forms for m-valued functions referred to as m-Reed-Muller canonical (m-RMC) forms that are a generalization of RMC forms of two-valued functions are proposed. m-RMC forms are based on the operations ?m (addition mod m) and .m (multiplication mod m) and do not, as in the cases of the generalizations proposed in the literature, require an m-valued function for m not a power of a prime, to be expressed by a canonical form for M-valued functions, where M > m is a power of a prime. Methods of obtaining the m-RMC forms from the truth vector or the sum of products representation of an m-valued function are discussed. Using a generalization of the Boolean difference to m-valued logic, series expansions for m-valued functions are derived.

Robust designs for Poisson regression models

We consider the problem of how to construct robust designs for Poisson regression models. An analytical expression is derived for robust designs for first-order Poisson regression models where uncertainty exists in the prior parameter estimates. Given certain constraints in the methodology, it may be necessary to extend the robust designs for implementation in practical experiments. With these extensions, our methodology constructs designs which perform similarly, in terms of estimation, to current techniques, and offers the solution in a more timely manner. We further apply this analytic result to cases where uncertainty exists in the linear predictor. The application of this methodology to practical design problems such as screening experiments is explored. Given the minimal prior knowledge that is usually available when conducting such experiments, it is recommended to derive designs robust across a variety of systems. However, incorporating such uncertainty into the design process can be a computationally intense exercise. Hence, our analytic approach is explored as an alternative.

Robust designs for Poisson regression models

We consider the problem of how to construct robust designs for Poisson regression models. An analytical expression is derived for robust designs for first-order Poisson regression models where uncertainty exists in the prior parameter estimates. Given certain constraints in the methodology, it may be necessary to extend the robust designs for implementation in practical experiments. With these extensions, our methodology constructs designs which perform similarly, in terms of estimation, to current techniques, and offers the solution in a more timely manner. We further apply this analytic result to cases where uncertainty exists in the linear predictor. The application of this methodology to practical design problems such as screening experiments is explored. Given the minimal prior knowledge that is usually available when conducting such experiments, it is recommended to derive designs robust across a variety of systems. However, incorporating such uncertainty into the design process can be a computationally intense exercise. Hence, our analytic approach is explored as an alternative.

Sensor fault-tolerant observer applied in satellite attitude control

The observing failure and feedback instability might happen when the partial sensors of a satellite attitude control system (SACS) go wrong. A fault diagnosis and isolation (FDI) method based on a fault observer is introduced to detect and isolate the fault sensor at first. Based on the FDI result, the object system state-space equation is transformed and divided into a corresponsive triangular canonical form to decouple the normal subsystem from the fault subsystem. And then the KX fault-tolerant observers of the system in different modes are designed and embedded into online monitoring. The outputs of all KX fault-tolerant observers are selected by the control switch process. That can make sense that the SACS is part-observed and in stable when the partial sensors break down. Simulation results demonstrate the effectiveness and superiority of the proposed method.

BOSTER : an efficient algorithm for mining frequent unordered induced subtrees

Extracting frequent subtrees from the tree structured data has important applications in Web mining. In this paper, we introduce a novel canonical form for rooted labelled unordered trees called the balanced-optimal-search canonical form (BOCF) that can handle the isomorphism problem efficiently. Using BOCF, we define a tree structure guided scheme based enumeration approach that systematically enumerates only the valid subtrees. Finally, we present the balanced optimal search tree miner (BOSTER) algorithm based on BOCF and the proposed enumeration approach, for finding frequent induced subtrees from a database of labelled rooted unordered trees. Experiments on the real datasets compare the efficiency of BOSTER over the two state-of-the-art algorithms for mining induced unordered subtrees, HybridTreeMiner and UNI3. The results are encouraging.

BEST : an efficient algorithm for mining frequent unordered embedded subtrees

This paper presents an algorithm for mining unordered embedded subtrees using the balanced-optimal-search canonical form (BOCF). A tree structure guided scheme based enumeration approach is defined using BOCF for systematically enumerating the valid subtrees only. Based on this canonical form and enumeration technique, the balanced optimal search embedded subtree mining algorithm (BEST) is introduced for mining embedded subtrees from a database of labelled rooted unordered trees. The extensive experiments on both synthetic and real datasets demonstrate the efficiency of BEST over the two state-of-the-art algorithms for mining embedded unordered subtrees, SLEUTH and U3.

Formal description, compression and transformation of digital pictures

This paper describes the application of vector spaces over Galois fields, for obtaining a formal description of a picture in the form of a very compact, non-redundant, unique syntactic code. Two different methods of encoding are described. Both these methods consist in identifying the given picture as a matrix (called picture matrix) over a finite field. In the first method, the eigenvalues and eigenvectors of this matrix are obtained. The eigenvector expansion theorem is then used to reconstruct the original matrix. If several of the eigenvalues happen to be zero this scheme results in a considerable compression. In the second method, the picture matrix is reduced to a primitive diagonal form (Hermite canonical form) by elementary row and column transformations. These sequences of elementary transformations constitute a unique and unambiguous syntactic code-called Hermite code—for reconstructing the picture from the primitive diagonal matrix. A good compression of the picture results, if the rank of the matrix is considerably lower than its order. An important aspect of this code is that it preserves the neighbourhood relations in the picture and the primitive remains invariant under translation, rotation, reflection, enlargement and replication. It is also possible to derive the codes for these transformed pictures from the Hermite code of the original picture by simple algebraic manipulation. This code will find extensive applications in picture compression, storage, retrieval, transmission and in designing pattern recognition and artificial intelligence systems.

A Note on Easily Testable Realizations for Logic Functions

It is shown that at most, n + 3 tests are required to detect any single stuck-at fault in an AND gate or a single faulty EXCLUSIVE OR (EOR) gate in a Reed-Muller canonical form realization of a switching function.

On the stabilization of uniformly decoupled systems by state variable feedback

Conditions under which the asymptotic stabilization of uniformly decoupled time-varying multivariate systems is possible are explored. This is accomplished by developing a canonical form for integrator uniformly decoupled system in which the coefficient matrices have a simple structure. The procedures developed rely on certain conditions on the given system and yield explicit expressions for the stabilization compensators.

A computational procedure to generate difference equations from differential equations

In this paper we have developed methods to compute maps from differential equations. We take two examples. First is the case of the harmonic oscillator and the second is the case of Duffing's equation. First we convert these equations to a canonical form. This is slightly nontrivial for the Duffing's equation. Then we show a method to extend these differential equations. In the second case, symbolic algebra needs to be used. Once the extensions are accomplished, various maps are generated. The Poincare sections are seen as a special case of such generated maps. Other applications are also discussed.