Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

Cyclic codes over R = Fp + uFp +?+ uFp with length pn

In this paper, all cyclic codes with length p^sn, (n prime to p) over the ring R = F_p + uF_p +?+ u^k−1F_p are classified. It is first proved that Tor_j(C) is an ideal of , so that the structure of ideals over extension ring S_u^k(m,ω)=GR(u^k,m)[ω]/〈ω^ps-1〉 is determined. Then, an isomorphism between R[X]/〈X^N − 1〉 and a direct sum ⊕_h∈IS_u^k(m_h,ω) can be obtained using discrete Fourier transform. The generator polynomial representation of the corresponding ideals over F_p + uF_p +?+ u^k−1F_p is calculated via the inverse isomorphism. Moreover, torsion codes, MS polynomial and inversion formula are described.     

On the structure of generalized rough sets

In this paper we consider some fundamental properties of generalized rough sets induced by binary relations on algebras and show that

1.

Any reflexive binary relation determines a topology.

2.

If θ is a reflexive and symmetric relation on a set X, then O={A⊆X|θ_-(A)=A} is a topology such that A is open if and only if it is closed.

3.

Conversely, for every topological space (X,O) satisfying the condition that A is open if and only if it is closed, there exists a reflexive and symmetric relation R such that O={A⊆X|R_-(A)=A}.

4.

Let θ be an equivalence relation on X. For any pseudo ω-closed subset A of X, θ₋(A) is an ω-closed set if and only if ω(x, x, … , x) ∈ θ₋(A) for any x ∈ X.

Moreover we consider properties of generalized rough sets.     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

A (4n − 9)/3 diagnosis algorithm on n-dimensional cube network

As a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis of multicomputers, the t/k diagnosis strategy can significantly improve the self-diagnosing capability of a system at the expense of no more than k fault-free processors (nodes) being mistakenly diagnosed as faulty. In the case k ? 2, to our knowledge, there is no known t/k diagnosis algorithm for general diagnosable system or for any specific system. Hypercube is a popular topology for interconnecting processors of multicomputers. It is known that an n-dimensional cube is (4n − 9)/3-diagnosable. This paper addresses the (4n − 9)/3 diagnosis of n-dimensional cube. By exploring the relationship between a largest connected component of the 0-test subgraph of a faulty hypercube and the distribution of the faulty nodes over the network, the fault diagnosis of an n-dimensional cube can be reduced to those of two constituent (n − 1)-dimensional cubes. On this basis, a diagnosis algorithm is presented. Given that there are no more than 4n − 9 faulty nodes, this algorithm can isolate all faulty nodes to within a set in which at most three nodes are fault-free. The proposed algorithm can operate in O(N log₂ N) time, where N = 2ⁿ is the total number of nodes of the hypercube. The work of this paper provides insight into developing efficient t/k diagnosis algorithms for larger k value and for other types of interconnection networks.     

The periodic nature of the positive solutions of a nonlinear fuzzy max-difference equation

We investigate the periodic nature of the positive solutions of the fuzzy difference equation , where k, m are positive integers, A₀, A₁, are positive fuzzy numbers and the initial values x_i, i = −d, −d + 1, … , −1, d = max{k, m}, are positive fuzzy numbers. In addition, we give conditions so that the solutions of this equation are unbounded.     

Existence of solutions to singular integral equations

Nonnegative solutions are established for singular integral equations of the form y(t) = h(t) + ∫^T₀ k(t, s)f(s, y(s)) ds for t ∈ [0, T]. Here f may be singular at y = 0.     

On conditional diagnosability of the folded hypercubes

The n-dimensional folded hypercube FQ_n, a variation of the hypercube proposed by Ahmed et al. [A. El-Amawy, S. Latifi, Properties and performance of folded hypercubes, IEEE Transactions on Parallel and Distributed Systems 2(3) (1991) 31-42], is an (n + 1)-regular (n + 1)-connected graph. Conditional diagnosability, a new measure of diagnosability introduced by Lai et al. [Pao-Lien Lai, Jimmy J.M. Tan, Chien-Ping Chuang, Lih-Hsing Hsu, Conditional diagnosability measures for large multiprocessor systems, IEEE Transactions on Computers 54(2) (2005) 165-175] can better measure the diagnosability of regular interconnection networks. This paper determines that under PMC-model the conditional diagnosability of FQ_n (t_c(FQ_n)) is 4n − 3 when n = 5 or n ? 8; t_c(FQ₃) = 3, t_c(FQ₄) = 7.     

The persistence probability and the price–price correlation functions in the Korean stock market

We consider the one minute time series of the Korean stock market index (KOSPI). We defined the persisting time as the time interval when the index remains above (or below) an initial index. We observed that the average persistence probability P(t) followed a power-law behavior like P(t)∼t−θ with the persistence exponent θ=0.477(2). The persistence exponent in the Korean stock market deviates slightly from a random process. The Korean stock market has shown a weak anti-persistence. We measured the persistence properties of the stock market by the generalized price–price correlation function Fq(t). The price–price correlation function followed a power law, Fq(t)∼thq, where hq is called the generalized Hurst exponent. The generalized Hurst exponent depends on the order q which means that there are multiscaling properties in the time series of the stock index. We observed the relationship θ+h₂=1 between the error bars where h₂ is the fractal dimension of the time series.     

Annual and interannual (ENSO) variability of spatial scaling properties of a vegetation index (NDVI) in Amazonia

The space-time variability of the Normalized Difference Vegetation Index (NDVI) over the Amazon River basin is quantified through the bi-dimensional Fourier spectrum, and moment-scaling analysis of monthly imagery at 8 km resolution, for the period July 1981-November 2002. Monthly NDVI fields exhibit power law Fourier spectra, E(k)=ck^−β, with k denoting the wavenumber, c the prefactor, and β the scaling exponent. Fourier spectra exhibit two scaling regimes separated at approximately 29 km, above which NDVI exhibit long-range spatial correlations (0<β<2), and below which NDVI behaves like white noise in space (β?0). Series of monthly values of c(t) and β(t) exhibit high negative correlation (−0.88, P>0.99), which suggest their linkages in power laws, but also that E_t(k)=c(t)k^−β(t), with t the time index. Results show a significant negative simultaneous correlation (−0.82, P>0.95) between monthly series of average precipitation over the Amazon, 〈P(t)〉, and scaling exponents, β(t); and high positive lagged correlation (0.63, P>0.95), between 〈P(t)〉 and 〈NDVI(t+3)〉. Parameters also reflect the hydrological seasonal cycle over Amazonia: during the wet season (November-March), β(t) ranges between 0.9 and 1.15, while during the dry season (May-September), β(t)?1.30. These results reflect the more (less) coherent spatial effect of the dry (wet) season over Amazonia, which translates into longer (shorter)-range spatial correlations of the NDVI field, as witnessed by higher (lower) values of β(t). At interannual timescales, both phases of ENSO reflect on both parameters, as β(t) is higher during El Niño than during La Niña, due to the more coherent effects of El Niño-related dryness, whereas NDVI spatial variability is enhanced during La Niña, due to positive rainfall anomalies. Results from the moment-scale analysis indicate the existence of multi-scaling in the spatial variability of NDVI fields. Departures from single scaling exhibit also annual and interannual variability, which consistently reflect the effects from both phases of ENSO. Furthermore, departures from single scaling are independent of the order moment, q, as the PDF of departures scaled by the mean collapse to a unique distribution. These results point out that ideas of spatial scaling constitute a promising framework to synthesize important hydro-ecological processes of Amazonia.     

Constructing vertex-disjoint paths in (n, k)-star graphs

This work describes a novel routing algorithm for constructing a container of width n − 1 between a pair of vertices in an (n, k)-star graph with connectivity n − 1. Since Lin et al. [T.C. Lin, D.R. Duh, H.C. Cheng, Wide diameter of (n, k)-star networks, in: Proceedings of the International Conference on Computing, Communications and Control Technologies, vol. 5, 2004, pp. 160-165] already calculated the wide diameters in (n, n − 1)-star and (n, 1)-star graphs, this study only considers an (n, k)-star with 2 ? k ? n − 2. The length of the longest container among all constructed containers serves as the upper bound of the wide diameter of an (n, k)-star graph. The lower bound of the wide diameter of an (n, k)-star graph with 2 ? k ? ⌊n/2⌋ and the lower bound of the wide diameter of a regular graph with a connectivity of 2 or above are also computed. Measurement results indicate that the wide diameter of an (n, k)-star graph is its diameter plus 2 for 2 ? k ? ⌊n/2⌋, or its diameter plus a value between 1 and 2 for ⌊n/2⌋ + 1 ? k ? n − 2.     

Embedding meshes into twisted-cubes

The n-dimensional twisted-cube, TN_n, is a variation of the hypercube. In this paper, we study embedding of meshes into TN_n. We prove three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded into TN_n with dilation 1 and expansion 1. (2) For any integer n ? 4, an m × k(m ? 3, k ? 3) mesh cannot be embedded into TN_n with dilation 1. (3) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded into TN_n with dilation 2 and expansion 1.     

The panpositionable panconnectedness of augmented cubes

A graph G is panconnected if, for any two distinct vertices x and y of G, it contains an [x, y]-path of length l for each integer l satisfying d_G(x, y) ? l ? ∣V(G)∣ − 1, where d_G(x, y) denotes the distance between vertices x and y in G, and V(G) denotes the vertex set of G. For insight into the concept of panconnectedness, we propose a more refined property, namely panpositionable panconnectedness. Let x, y, and z be any three distinct vertices in a graph G. Then G is said to be panpositionably panconnected if for any d_G(x, z) ? l₁ ? ∣V(G)∣ − d_G(y, z) − 1, it contains a path P such that x is the beginning vertex of P, z is the (l₁ + 1)th vertex of P, and y is the (l₁ + l₂ + 1)th vertex of P for any integer l₂ satisfying d_G(y, z) ? l₂ ? ∣V(G)∣ − l₁ − 1. The augmented cube, proposed by Choudum and Sunitha [6] to be an enhancement of the n-cube Q_n, not only retains some attractive characteristics of Q_n but also possesses many distinguishing properties of which Q_n lacks. In this paper, we investigate the panpositionable panconnectedness with respect to the class of augmented cubes. As a consequence, many topological properties related to cycle and path embedding in augmented cubes, such as pancyclicity, panconnectedness, and panpositionable Hamiltonicity, can be drawn from our results.     

Characterization of analytic phase signals

In many cases, a real-valued signal χ(t) may be associated with a complex-valued signal a(t)e^iθ(t), the analytic signal associated with χ(t) with the characteristic properties χ(t) = a(t) cosθ(t) and H(a(·)cosθ(·))(t) = a(t)sinθ(t). Using such obtained amplitude-frequency modulation the instantaneous frequency of χ(t) at the time t₀ may be defined to be θ′(t₀), provided θ′(t₀) ≥ 0. The purpose of this note is to characterize, in terms of analytic functions, the unimodular functions F(t) = C(t) + iS(t),C²(t) + S² (t) = 1, a.e., that satisfy HC(t) = S(t). This corresponds to the case a(t) ≡ 1 in the above formulation. We show that a unimodular function satisfies the required condition if and only if it is the boundary value of a so called inner function in the upper-half complex plane. We also give, through an explicit formula, a large class of functions of which the parametrization C(t) = cosθ(t) is available and the extra condition θ′(t) ≥ 0, a.e. is enjoyed. This class of functions contains Blaschke products in the upper-half complex plane as a proper subclass studied by Picinbono in [1].     

Steiner systems <Emphasis Type="Italic">S</Emphasis>(<Emphasis Type="Italic">v,k, k</Emphasis> − 1): Components and rank

For an arbitrary Steiner system S(v, k, t), we introduce the concept of a component as a subset of a system which can be transformed (changed by another subset) without losing the property for the resulting system to be a Steiner system S(v, k, t). Thus, a component allows one to build new Steiner systems with the same parameters as an initial system. For an arbitrary Steiner system S(v, k, k − 1), we provide two recursive construction methods for infinite families of components (for both a fixed and growing k). Examples of such components are considered for Steiner triple systems S(v, 3, 2) and Steiner quadruple systems S(v, 4, 3). For such systems and for a special type of so-called normal components, we find a necessary and sufficient condition for the 2-rank of a system (i.e., its rank over \mathbbF₂\mathbb{F}_2) to grow under switching of a component. It is proved that for k ≥ 5 arbitrary Steiner systems S(v, k, k − 1) and S(v, k, k − 2) have maximum possible 2-ranks.     

Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with f_v faulty nodes and f_e faulty edges lies in a fault-free cycle of every even length from 4 to kⁿ − 2f_v (resp. kⁿ − f_v) if k ? 4 is even (resp. k ? 3 is odd) and f_v + f_e ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.     

An efficient parity detection technique using the two-moduli set {2 − 1, 2 + 1}

Lu and Chiang used both the table lookup and fractional number approaches to discover the parity of an RNS number. To eliminate the need for table space and time for computing fractions, a two-moduli set {2^h − 1, 2^h + 1} is used to speed up the technique proposed by Lu and Chiang. Based on this modified two-moduli set, it is found that the parity of an RNS number X = (x₁, x₂) is if x₁ ? x₂. On the contrary, if x₁ < x₂, the parity of X is .     

A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees

Let G be a graph. Then T ⊆ V(G) is called an R^k-vertex-cut if G − T is disconnected and each vertex in V(G) − T has at least k neighbors in G − T. The size of a smallest R^k-vertex-cut is the R^k-vertex-connectivity of G and is denoted by κ^k(G). In this paper, we determine the numbers κ¹ and κ² for Cayley graphs generated by 2-trees, including the popular alternating group graphs.     

Asymptotic behavior and blow up of solutions for semilinear parabolic equations at critical energy level

In this paper we study the initial boundary value problem of semilinear parabolic equations with semilinear term f(u). By using the family of potential wells method we prove that if f(u) satisfies some conditions, J(u₀) ≤ d and I(u₀) > 0, then the solution decays to zero exponentially as t → ∞. On the other hand, if J(u₀) ≤ d, I(u₀) < 0, then the solution blows up in finite time.     

Stability of θ-methods for advanced differential equations with piecewise continuous arguments

This paper deals with the stability analysis of numerical methods for the solution of advanced differential equations with piecewise continuous arguments. We focus on the behaviour of the one-leg θ-method and the linear θ-method in the solution of the equation x′(t) = ax(t + a₀x([t]) + a₁x([t+1]), with real a, a₀, a₁ and [·] designates the greatest-integer function. The stability regions of two θ-methods are determined. The conditions under which the analytic stability region is contained in the numerical stability region are obtained and some numerical experiments are given.