A recursive algorithm for the reliability of a circular connected-(r,s)-out-of-(m,n):F lattice system

A circular connected-(r, s)-out-of-(m, n):F lattice system consists of m×n components arranged in a cylindrical grid. Each of m circles has n components, and this system fails if and only if there exists a grid of size r ×s which all components are failed. A circular connected-(r, s)-out-of-(m, n):F lattice system might be used in reliability models for ‘Feelers for measuring temperature on reaction chamber’ and ‘TFT Liquid Crystal Display system with 360° wide area’.In this study, we proposed a new recursive algorithm for obtaining the reliability of a circular connected-(r, s)-out-of-(m, n):F lattice system. We evaluated our proposed algorithms in terms of computing time and memory capacity. Furthermore, a numerical experiment comparing our proposed algorithm with Yamamoto and Miyakawa's algorithm [Yamamoto, H., & Miyakawa, M. (1996). Reliability of circular connected-(r, s)-out-of-(m, n):F lattice system. Journal of the Operations Research Society of Japan, 39(3), 389–406] showed that our proposed algorithm is more effective for systems with a large n.     

Constrained (k,d)-out-of-n systems

Two new coherent system reliability models, which generalise k-out-of-n:F and consecutive k-out-of-n:G systems, are proposed and explicit formulae for the reliabilities of these systems are derived when the components are independent and identical and when they are Markov dependent. Our method of deriving reliability functions is based on the use of classical combinatorial arguments. These extensions consider an additional constraint on the number of working components between successive failures. More explicitly, in addition to the working conditions of k-out-of-n:F and consecutive k-out-of-n:G systems there must be at least d consecutive working components between any of two successive failures. This type of consideration might be useful in some situations including the analysis of constrained binary sequences arising in communications systems, and particular infrared detecting systems.     

On a generalized k-out-of-n system and its reliability

A consecutive-k-out-of-n system is a system with n components arranged either linearly or circularly, which fails if and only if at least k consecutive components fail. An (n,?f,?k) system further requires that the total number of failed components is less than f for the system to be working. Here we consider a more general system consisting of N modules with the ith module-composed of n _i components in parallel; the system fails if and only if there exist at least f failed components or at least k consecutive failed modules. In this paper, some formulae for the reliability of such a generalized k-out-of-n system are derived for both the linear and the circular cases. The recursive formulae established here can be easily computed. Many existing results are also shown to be special cases of the results obtained in this paper. Furthermore, we investigate some component importance properties.     

AnO(n 3) recognition algorithm for bithreshold graphs

A bithreshold graph is the edge intersection of two threshold graphs such that every independent set is independent in at least one of the threshold components. Recognizing a bithreshold graph is polynomially equivalent to recognizing its complement, i.e., a cobithreshold graph. In this paper we introduce a coloring of the vertices and of the edges of a cobithreshold graph that leads to a recognition and decomposition algorithm. This algorithm works inO(n ³) time improving the previously knownO(n ⁴) result [HM].     

New (n, r)-arcs in PG(2, 17), PG(2, 19), and PG(2, 23)

An (n, r)-arc is a set of n points of a projective plane such that some r but no r+1 of them are collinear. The maximum size of an (n, r)-arc in PG(2, q) is denoted by m _r (2, q). In this paper a new (95, 7)-arc, (183, 12)-arc, and (205, 13)-arc in PG(2, 17) are constructed, as well as a (243, 14)-arc and (264, 15)-arc in PG(2, 19). Likewise, good large (n, r)-arcs in PG(2, 23) are constructed and a table with bounds on m _r (2, 23) is presented. In this way many new 3-dimensional Griesmer codes are obtained. The results are obtained by nonexhaustive local computer search.     

Asymptotic Upper Bound for the Rate of (w,r) Cover-Free Codes

A binary code is called a (w, r) cover-free code if it is the incidence matrix of a family of sets where the intersection of any w of the sets is not covered by the union of any other r sets. Such a family is called a (w, r) cover-free family. We obtain a new recurrent inequality for the rate of (w, r) cover-free codes, which improves previously known upper bounds on the rate.     

An O(n log n) Average Time Algorithm for Computing the Shortest Network under a Given Topology

In 1992 F. K. Hwang and J. F. Weng published an O(n ² ) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane. The Hwang—Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang—Weng algorithm. While the worst-case time complexity of our algorithm is still O(n ² ) , its average time complexity over all the full Steiner topologies interconnecting n fixed points is O (n log n ). Received August 24, 1996; revised February 10, 1997.     

(n,N) type maintenance policy for multi-component systems with failure interactions

This paper studies maintenance policies for multi-component systems in which failure interactions and opportunistic maintenance (OM) involve. This maintenance problem can be formulated as a Markov decision process (MDP). However, since an action set and state space in MDP exponentially expand as the number of components increase, traditional approaches are computationally intractable. To deal with curse of dimensionality, we decompose such a multi-component system into mutually influential single-component systems. Each single-component system is formulated as an MDP with the objective of minimising its long-run average maintenance cost. Under some reasonable assumptions, we prove the existence of the optimal (n, N) type policy for a single-component system. An algorithm to obtain the optimal (n, N) type policy is also proposed. Based on the proposed algorithm, we develop an iterative approximation algorithm to obtain an acceptable maintenance policy for a multi-component system. Numerical examples find that failure interactions and OM pose significant effects on a maintenance policy.     

Construction of solitary wave solutions for variants of the K(n,n) equation

In this paper, variational iteration method and Adomian decomposition are implemented to construct solitary solutions for variants of K(n, n) equation. In these schemes the solution takes the form of a convergent series with easily computable components. The chosen initial solution or trial function plays a major role in changing the physical structure of the solution. Comparison between the two methods is made and many models are approached. The obtained results reveal that the two methods are very effective and convenient for constructing solitary solutions.     

Some characterizations of finitely specifiable implicational dependency families

Let r be a relation for the relation scheme R(A₁,A₂,…,A_n); then we define Dom(r) to be Dom_r(A₁)×Dom_r(A₂)×…×Dom_r(A_n), where Dom_r(A_i) for each i is the set of all ith coordinates of tuples of r. A relation s is said to be a substructure of the relation r if and only if Dom(s)∩r = s.The following theorems analogous to Tarski-Fraisse-Vaught's characterizations of universal classes are proved: (i) An implicational dependency family (ID-family) F over the relation scheme R is finitely specifiable if and only if there exists a finite number of relations r₁,r₂,…,r_m for R such that r ∈ F if and only if no r_i is isomorphic to a substructure of r. (ii) F is finitely specifiable if and only if there exists a natural number k such that r ∈ F whenever F contains all substructures of r with at most k elements.We shall use these characterizations to obtain a new proof for Hull's (1984) characterization of finitely specifiable ID-families.     

On the Optimality of Trivial (w,r)-Cover-Free Codes

A (w, r)-cover-free code is the incidence matrix of a family of sets where no intersection of w members of the family is covered by the union of r others. We obtain a new condition in view of which (w, r)-cover-free codes with a simple structure are optimal. We also introduce (w, r)-cover-free codes with a constraint set.     

Treemap: An O(log n) algorithm for indoor simultaneous localization and mapping

This article presents a very efficient SLAM algorithm that works by hierarchically dividing a map into local regions and subregions. At each level of the hierarchy each region stores a matrix representing some of the landmarks contained in this region. To keep those matrices small, only those landmarks are represented that are observable from outside the region. A measurement is integrated into a local subregion using O(k²) computation time for k landmarks in a subregion. When the robot moves to a different subregion a full least-square estimate for that region is computed in only O(k³ log n) computation time for n landmarks. A global least square estimate needs O(kn) computation time with a very small constant (12.37 ms for n = 11300). The algorithm is evaluated for map quality, storage space and computation time using simulated and real experiments in an office environment. This article is based on the authors studies at the German Aerospace Center. Udo Frese was born in Minden, Germany in 1972. He received the Diploma degree in computer science from the University of Paderborn in 1997. From 1998 to 2003 he was a Ph.D. student at the German Aerospace Center in Oberpfaffenhofen. In 2004 he received his Ph.D. degree from University of Erlangen-Nürnberg and joined SFB/TR 8 Spatial Cognition at University of Bremen. He works on mobile robotics, SLAM and computer vision.     

L(2, 1)-labellings for direct products of a triangle and a cycle

An L(2, 1)-labelling of a graph G is a vertex labelling such that the difference of the labels of any two adjacent vertices is at least 2 and that of any two vertices of distance 2 is at least 1. The minimum span of all L(2, 1)-labellings of G is the λ-number of G and denoted by λ(G). Lin and Lam computed λ(G) for a direct product G=K _m ×P _n of a complete graph K _m and a path P _n . This is a natural lower bound of λ(K _m ×C _n ) for a cycle C _n . They also proved that when n≡ 0±od 5m, this bound is the exact value of λ(K _m ×C _n ) and computed the value when n=3, 5, 6. In this article, we compute the λ-number of G, where G is the direct product K ₃×C _n of the triangle and a cycle C _n for all the other n. In fact, we show that among these n, λ(K ₃×C _n )=7 for all n≠7, 11 and λ(K ₃×C _n )=8 when n=7, 11.     

Metal (IV) tetras (8‐hydroxyquinoline) (M = Zr,Hf) used as electroluminescent material and electron‐transport layer in OLEDs

Abstract— In this paper, we report on the utilization of zirconium (IV) tetras (8‐hydroxyquinoline), Zrq₄, and hafnium (IV) tetras (8‐hydroxyquinoline), Hfq₄, as an electroluminescent material in fluorescent organic light‐emitting diodes (OLED) and as electron transport layer (ETL) for high‐efficiency electrophosphorescent organic light‐emitting diodes (PHOLEDs). Structural studies show that the metal tetraquinolates (Mq₄) have a very low dipole moment (<0.1 D), in contrast to Alq₃ which has an estimated dipole moment of 4.7 D. Mobility measurements show that Mq₄ complexes give mobilities of (3.5 ± 0.5) × 10^?6 cm²/V‐sec, which are close to the values reported for Alq₃, i.e., (2.3–4.3) × 10^?6 cm²/V‐sec. OLEDs were prepared with the structure ITO/NPD (400 Å)/Mq_n (500 Å)/LiF/Al (NPD = 4‐4′‐bis[N‐(1‐naphthyl)‐N‐phenyl‐amino]bi phenyl, Mq_n = Alq₃, Zrq₄, Hfq₄. The Mq₄‐based OLEDs gave external efficiencies of 1.1%, while the Alq₃‐based devices of the same structure gave efficiencies of 0.7%. PHOLEDs have been fabricated with the structure ITO/NPD (500 Å)/CBP‐8% Ir(ppy)³ (250 Å)/BCP (150 Å)/Mq_n (250 Å)/LiF/Al (CBP = N,N′‐dicarbazolyl‐4‐4′‐biphenyl, Ir(ppy)³ = fac‐tris(2‐phenylpyrridine)iridium, BCP = bathocruprione). PHOLEDs with Mq₄ ETLs showed a greatly improved efficiency, when compared to Alq₃‐based PHOLEDs. The Zrq₄‐based PHOLEDs gave a peak external quantum efficiency of 14% at 0.3 mA/cm² (150 cd/m²), while the Hfq₄ based PHOLED gave a peak external quantum efficiency of 15% at 0.6 mA/cm² (300 cd/m²). Comparable PHOLEDs with an Alq₃ ETL give peak external quantum efficiencies of 8.0% at 0.5 mA/cm². The devices gave an electroluminescence (EL) spectrum consisting only of fac‐tris(2‐phenylpyrridine)iridium (Ir(ppy)³) dopant emission (CIE coordinates of 0.26, 0.66), with no Mq₄ emission observed at any bias level.     

Binding number and Hamiltonian (g,f)-factors in graphs II

A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N _G (X)= gcup _x∈X N _G (x). The binding number of G is defined by bind(G)=min{| N _G (X) |/| X|| ?≠X?V(G), N _G (X)≠V(G)}. Let G be a connected graph of order n, 3≤a≤b be integers, and b≥4. Let g, f be positive integer-valued functions defined on V(G), such that a≤g(x)≤f(x)≤b for every x∈V(G). Suppose n≥(a+b?4)²/(a?2) and f(V(G)) is even, we shall prove that if bind(G)>((a+b?4)(n?1))/((a?2)n?(5/2)(a+b?4)) and for any independent set X?V(G), N _G (X)≥((b?3)n+(2a+2b?9)| X|)/(a+b?5), then G has a Hamiltonian (g, f)-factor.     

Computations on Nondeterministic Cellular Automata

This work concerns the trade-offs between the dimension and the time and space complexity of computations on nondeterministic cellular automata. We assume that the space complexity is the diameter of area in space involved in computation. It is proved that (1) every nondeterministic cellular automata (NCA) of dimensionr, computing a predicatePwith time complexityT(n) and space complexityS(n) can be simulated byr-dimensional NCA with time and space complexityO(T^1/(r+1)S^r/(r+1)) and byr+1 dimensional NCA with time and space complexityO(T^1/2+S), whereTandSare functions constructible in time, (2) for any predicatePand integerr>1 if is a fastestr-dimensional NCA computingPwith time complexityT(n) and space complexityS(n), thenT=O(S), and (3) ifT_{r, P}is the time complexity of a fastestr-dimensional NCA computing predicatePthenT_r+1,P=O((T_{r, P})^1−r/(r+1)2),T_r+1,P=O((T_{r, P})^1+2/r).Similar problems for deterministic cellular automata (CA) are discussed.     

Solution‐processable double‐layered ionic p‐i‐n organic light‐emitting diodes

Abstract— Solution‐processed double‐layered ionic p‐i‐n organic light‐emitting diodes (OLEDs), comprised of an emitting material layer doped with an organometallic green phosphor and a photo‐cross‐linked hole‐transporting layer doped with photo‐initiator is reported. The fabricated OLEDs were annealed using simultaneous thermal and electrical treatments to form a double‐layered ionic p‐i‐n structure. As a result, an annealed double‐layered OLED with a peak brightness over 20,000 cd/m² (20 V, 390 mA/cm²) and a peak efficiency of 15 cd/A (6 V, 210 cd/m²) was achieved.     

Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2

Summary Polynomial multiplication of degree N can be accomplished in time O (N · log N) provided the scalar field contains suitable roots of unity. Otherwise at least O (N · log N · log log N) is obtained by a modified version of the Schönhage-Strassen multiplication which employs computations modulo 1 + xⁿ (where N = 2ⁿ), if the field contains 2^–1, or modulo 1 + xⁿ + x^2N, if 3^–1 exists. The latter method covering all fields of characteristic 2 is presented here in detail.     

Strong-Diameter Decompositions of Minor Free Graphs

We provide the first sparse covers and probabilistic partitions for graphs excluding a fixed minor that have strong diameter bounds; i.e. each set of the cover/partition has a small diameter as an induced sub-graph. Using these results we provide improved distributed name-independent routing schemes. Specifically, given a graph excluding a minor on r vertices and a parameter ρ>0 we obtain the following results: (1) a polynomial algorithm that constructs a set of clusters such that each cluster has a strong-diameter of O(r ² ρ) and each vertex belongs to 2 ^O(r) r! clusters; (2) a name-independent routing scheme with a stretch of O(r ²), headers of O(log n+rlog r) bits, and tables of size 2 ^O(r) r! log ⁴ n/log log n bits; (3) a randomized algorithm that partitions the graph such that each cluster has strong-diameter O(r6 ^r ρ) and the probability an edge (u,v) is cut is O(r  d(u,v)/ρ).     

A Deterministic Construction of Normal Bases With Complexity O(n3 + n log n log(log n) log q)

Constructing normal bases of GF(qⁿ) over GF (q) can be done by probabilistic methods as well as deterministic ones. In the following paper we consider only deterministic constructions. As far as we know, the best complexity for probabilistic algorithms is O(n² log⁴n log² (log n) + n log n log (log n) log q ) (see von zur Gathen and Shoup, 1992). For deterministic constructions, some prior ones, e.g. Lueneburg (1986), do not use the factorization of Xⁿ - 1 over GF(q). As analysed by Bach, Driscoll and Shallit (1993), the best complexity (from Lueneburg, 1986) is O(n³ log n log(log n) + n² log n log(log n) log q). For other deterministic constructions, which need such a factorization, the best complexities are O(n^3,376 + n² log n log(log n) log q) (von zur Gathen and Giesbrecht, 1990), or O(n³ log q); see Augot and Camion (1993). Here we propose a new deterministic construction that does not require the factorization of Xⁿ - 1. Its complexity is reduced to O (n³ + n log n log(log n) log q ).