A study of connectivity on dynamic graphs: computing persistent connected components

4OR - This work focuses on connectivity in a dynamic graph. An undirected graph is defined on a finite and discrete time interval. Edges can appear and disappear over time. The first objective of...     

A random maintenance scheduling model to reduce fault diagnosis time

We present a random model for a situation in which some tests of fault detection are to be scheduled to diagnose what type of fault, out of some possible types of faults, has occurred. There are two variants of the model. In the first, the objective is average total diagnosis time. In the second, the objective is a linear combination of average and standard deviation of the diagnosis time, where standard deviation is multiplied with a positive weight. We give an exact solution method for the first case and a heuristic method for the second. A numerical experiment with randomly generated instances is done for the heuristic method. The methods appear to be suitable for practical applications.     

Multi-scale anomaly detection algorithm based on infrequent pattern of time series

In this paper, we propose two anomaly detection algorithms PAV and MPAV on time series. The first basic idea of this paper defines that the anomaly pattern is the most infrequent time series pattern, which is the lowest support pattern. The second basic idea of this paper is that PAV detects directly anomalies in the original time series, and MPAV algorithm extraction anomaly in the wavelet approximation coefficient of the time series. For complexity analyses, as the wavelet transform have the functions to compress data, filter noise, and maintain the basic form of time series, the MPAV algorithm, while maintaining the accuracy of the algorithm improves the efficiency. As PAV and MPAV algorithms are simple and easy to realize without training, this proposed multi-scale anomaly detection algorithm based on infrequent pattern of time series can therefore be proved to be very useful for computer science applications.     

The occurrence of sequence patterns in ergodic Markov chains

The occupation measure identity is used to derive the expected waiting time for the first occurrence of a fixed finite pattern in a sequence of observations generated by an ergodic Markov chain.     

How homogeneous can the last appearing pattern be?

Given a sequence of indepent, uniformly distributed random letters coming from a finite alphabet, we are interested in the word (pattern) which is the last to be observed for the first time among all words of length n. We derive anas. result on the homogeneity of this last appearing pattern as a corollary of a more general theorem. © 1993 John Wiley & Sons, Inc.     

Waiting times for clumps of patterns and for structured motifs in random sequences

This paper provides exact probability results for waiting times associated with occurrences of two types of motifs in a random sequence. First, we provide an explicit expression for the probability generating function of the interarrival time between two clumps of a pattern. It allows, in particular, to measure the quality of the Poisson approximation which is currently used for evaluation of the distribution of the number of clumps of a pattern. Second, we provide explicit expressions for the probability generating functions of both the waiting time until the first occurrence, and the interarrival time between consecutive occurrences, of a structured motif. Distributional results for structured motifs are of interest in genome analysis because such motifs are promoter candidates. As an application, we determine significant structured motifs in a data set of DNA regulatory sequences.     

Waiting time problems for a two-dimensional pattern

We consider waiting time problems for a two-dimensional pattern in a sequence of i.i.d. random vectors each of whose entries is 0 or 1. We deal with a two-dimensional pattern with a general shape in the two-dimensional lattice which is generated by the above sequence of random vectors. A general method for obtaining the exact distribution of the waiting time for the first occurrence of the pattern in the sequence is presented. The method is an extension of the method of conditional probability generating functions and it is very suitable for computations with computer algebra systems as well as usual numerical computations. Computational results applied to computation of exact system reliability are also given. Department of Statistical Science, School of Mathematical and Physical Science, The Graduate University for Advanced Studies This research was partially supported by the ISM Cooperative Research Program (2002-ISM-CRP-2007).     

Exact solutions of Stokes’ first problem for heated generalized Burgers’ fluid in a porous half-space

This work is concerned with applying the fractional calculus approach to the fundamental Stokes’ first problem of a heated Burgers’ fluid in a porous half-space. Modified Darcy's law for a Burgers’ fluid with fractional model is introduced first time. By using the Fourier sine transform and the fractional Laplace transform, exact solutions of the velocity and temperature field are obtained. The solutions for a Navier–Stokes, second grade, Maxwell, Oldroyd-B or Burgers’ fluid appear as the limiting cases of the present analysis.     

Towards a unification of certain characterizations by conditional expectations

The paper presents a characterization of a general family of distributions by the form of the expectation of an appropriately truncated function of the random variable involved. The obtained result unifies results existing in the literature for specific distributions as well as new results that appear for the first time in this paper. A discrete version is also provided unifying existing characterizations of known discrete distributions.     

A functional partial differential equation arising in a cell growth model with dispersion

In this paper we solve an initial‐boundary value problem that involves a pde with a nonlocal term. The problem comes from a cell division model where the growth is assumed to be stochastic. The deterministic version of this problem yields a first‐order pde; the stochastic version yields a second‐order parabolic pde. There are no general methods for solving such problems even for the simplest cases owing to the nonlocal term. Although a solution method was devised for the simplest version of the first‐order case, the analysis does not readily extend to the second‐order case. We develop a method for solving the second‐order case and obtain the exact solution in a form that allows us to study the long time asymptotic behaviour of solutions and the impact of the dispersion term. We establish the existence of a large time attracting solution towards which solutions converge exponentially in time. The dispersion term does not appear in the exponential rate of convergence.     

Nonreflecting boundary condition for the wave equation

To solve the time-dependent wave equation in an infinite two (three) dimensional domain a circular (spherical) artificial boundary is introduced to restrict the computational domain. To determine the nonreflecting boundary we solve the exterior Dirichlet problem which involves the inverse Fourier transform. The truncation of the continued fraction representation of the ratio of Hankel function, that appear in the inverse Fourier transform, provides a stable and numerically accurate approximation. Consequently, there is a sequence of boundary conditions in both two and three dimensions that are new. Furthermore, only the first derivatives in space and time appear and the coefficients are updated in a simple way from the previous time step. The accuracy of the boundary conditions is illustrated using a point source and the finite difference solution to a Dirichlet problem.     

Approximation and attractivity properties of the degenerated Ginzburg-Landau equation

We are interested in spatially extended pattern forming systems close to the threshold of the first instability in case when the so-called degenerated Ginzburg-Landau equation takes the role of the classical Ginzburg-Landau equation as the amplitude equation of the system. This is the case when the relevant nonlinear terms vanish at the bifurcation point. Here we prove that in this situation every small solution of the pattern forming system develops in such a way that after a certain time it can be approximated by the solutions of the degenerated Ginzburg-Landau equation. In this paper we restrict ourselves to a Swift-Hohenberg-Kuramoto-Shivashinsky equation as a model for such a pattern forming system.     

Exact algorithm for generating two-segment cutting patterns of punched strips

Metal plates are often divided into items in two stages. First a guillotine shear cuts the plate into strips at the shearing stage, and then a stamping press punches out the items from the strips at the punching stage. This paper presents an algorithm for generating optimal two-segment cutting patterns of strips at the shearing stage. An orthogonal cut divides the plate into two segments, each of which contains strips of the same direction and length. The algorithm uses dynamic programming techniques to determine the optimal strip layouts on segments of various lengths, and selects two segments to appear in the optimal pattern. The segments are considered in increasing order of their lengths, so that dominant properties can be used to shorten the computation time. The computational results indicate that the algorithm is efficient in both material utilization and computation time.     

Hadamard’s Formula Inside and Out

Our goal is to explore boundary variations of spectral problems from the calculus of moving surfaces point of view. Hadamard’s famous formula for simple Laplace eigenvalues under Dirichlet boundary conditions is generalized in a number of significant ways, including Neumann and mixed boundary conditions, multiple eigenvalues, and second order variations. Some of these formulas appear for the first time here. Furthermore, we present an analytical framework for deriving general formulas of the Hadamard type.     

Feynman-Kac Particle Integration with Geometric Interacting Jumps

This article is concerned with the design and analysis of discrete time Feynman-Kac particle integration models with geometric interacting jump processes. We analyze two general types of model, corresponding to whether the reference process is in continuous or discrete time. For the former, we consider discrete generation particle models defined by arbitrarily fine time mesh approximations of the Feynman-Kac models with continuous time path integrals. For the latter, we assume that the discrete process is observed at integer times and we design new approximation models with geometric interacting jumps in terms of a sequence of intermediate time steps between the integers. In both situations, we provide nonasymptotic bias and variance theorems w.r.t. the time step and the size of the system, yielding what appear to be the first results of this type for this class of Feynman-Kac particle integration models. We also discuss uniform convergence estimates w.r.t. the time horizon. Our approach is based on an original semigroup analysis with first order decompositions of the fluctuation errors.     

Upper and Lower Bounds for the Lengths of Steiner Trees in 3-Space

We present a method of determining upper and lower bounds for the length of a Steiner minimal tree in 3-space whose topology is a given full Steiner topology, or a degenerate form of that full Steiner topology. The bounds are tight, in the sense that they are exactly satisfied for some configurations. This represents the first nontrivial lower bound to appear in the literature. The bounds are developed by first studying properties of Simpson lines in both two and three dimensional space, and then introducing a class of easily constructed trees, called midpoint trees, which provide the upper and lower bounds. These bounds can be constructed in quadratic time. Finally, we discuss strategies for improving the lower bound.Supported by a grant from the Australia Research Council.     

Weibull过程将来第k次失效时间的Bayes预测区间

具Weibull强度函数的非齐次Poisson过程经常被用来分析可修系统的失效模式.基于极大似然估计,Engelhardt ＆ Bain(1978)导出了Weibull过程将来第k次失效时间的经典预测区间.在本文中,我们用无信息联合验前分布,根据Weibull过程的前n次失效时间,给出了建立将来第k次失效时间的Bayes预测区间的方法,并说明了如何应用这些方法。     

Space Efficient Suffix Trees

We give first the representation of a suffix tree that uses n lg n + O(n) bits of space and supports searching for a pattern string in the given text (from a fixed size alphabet) in O(m) time, where n is the size of the text and m is the length of the pattern. The structure is quite simple and answers a question raised by Muthukrishnan (in Proceedings of the FST and TCS Preconference Workshop on Randomization, 1997, pp. 23–27). Previous compact representations of suffix trees had either a higher lower order term in space and had some expectation assumption or required more time for searching. When the size of the alphabet k is not viewed as a constant, this structure can be modified to use the same space but take O(m lg k) time for string searching or to use an additional O(n lg k) bits but take the same O(m) time for searching. We then give several index structures for binary texts, with less space including

• a structure that uses a suffix array (lg  bits) and an additional () bits,

• an indexing structure that takes bits of space, and

• an ( lg ) bit structure which answers in () time, the decision question of whether a given pattern of length occurs in the text.

Each of these structures uses a different technique, either in the storage scheme or in the search algorithm, in reducing the space requirement. The first one uses a suffix array, a sparse suffix tree, and a table structure. Finding all the occurrences of a pattern using this structure takes O(m + s) time, where s is the number of occurrences of the pattern in the text. The second structure constructs a sparse suffix tree for all the suffixes that start with the bit that occurs more times in the given binary text. The last structure uses an iterative algorithm to search for the pattern. This structure is the first o(n lg n) bit index to support the decision version of indexing queries in time linear in the length of the pattern. But this does not support the general indexing queries where we want to find the position of the occurrence of the pattern.Our main contribution is the development of techniques to use the succinct tree representation through balanced parentheses for suffix trees.     

Gauss数环中的素元

对于 Gauss数环 Z[i]={ a+ bi| a,b∈ Z}中的素元 ,给出了其整数中的素元形式为可表成 4 n+ 3的素数 ,非整数素元为其范数 N( α)为一素数的形式