On the number of full levels in tries

We study the asymptotic distribution of the fill‐up level in a binary trie built over n independent strings generated by a biased memoryless source. The fill‐up level is the number of full levels in a tree. A level is full if it contains the maximum allowable number of nodes (e.g., in a binary tree level k can have up to 2^k nodes). The fill‐up level finds many interesting applications, e.g., in the internet IP lookup problem and in the analysis of level compressed tries (LC tries). In this paper, we present a complete asymptotic characterization of the fill‐up distribution. In particular, we prove that this distribution concentrates on one or two points around the most probably value k = ?log_1/qn ? log log log n + 1 + log log(p/q)?, where p > q = 1 ? p is the probability of generating the more likely symbol (while q = 1 ? p is the probability of the less likely symbol). We derive our results by analytic methods such as generating functions, Mellin transform, the saddle point method, and analytic depoissonization. We also present some numerical verification of our results. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

The analysis of volatile trace compounds in landfill gases,compost heaps and forest air

Landfill gas, cryotrapped on a loop fashioned from a length of a capillary gas chromatography (GC) column, was examined for volatile organometallic compounds (VOMCs) and for volatile organic compounds (VOCs) by using GC–mass spectrometry (MS). A large number of organic components were present and many were identified, but the only VOMCs present in high enough concentrations to be detected were trimethylstibine and tetramethyltin. The use of inductively coupled plasma (ICP)‐MS as an element‐specific detector allowed the identification of a number of other organometallic species in the landfill gas, including trimethylarsine and trimethylbismuth, and, for the first time, butyltrimethyltin and dibutyldimethyltin. The presence of molybdenum hexacarbonyl was confirmed. Gas from a large‐scale compost heap and from compost incubated in the laboratory contained iodomethane but no common VOMCs (GC–ICP‐MS). Only VOCs were present in forest air (GC–MS). Copyright © 2003 John Wiley & Sons, Ltd.     

Mass‐lumping or not mass‐lumping for eigenvalue problems

In this article we analyze the effect of mass‐lumping in the linear triangular finite element approximation of second‐order elliptic eigenvalue problems. We prove that the eigenvalue obtained by using mass‐lumping is always below the one obtained with exact integration. For singular eigenfunctions, as those arising in non convex polygons, we prove that the eigenvalue obtained with mass‐lumping is above the exact eigenvalue when the mesh size is small enough. So, we conclude that the use of mass‐lumping is convenient in the singular case. When the eigenfunction is smooth several numerical experiments suggest that the eigenvalue computed with mass‐lumping is below the exact one if the mesh is not too coarse. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 653–664, 2003     

Depth profile analysis of polyimide film treated by potassium hydroxide

The structural change in the depth direction of a polyimide (UPILEX‐S) film treated in alkaline solution, which was a representative surface treatment used to form a seed layer for plating and to improve the adhesive strength, was analyzed by means of micro Fourier transform infrared attenuated total reflection (FTIR‐ATR) line analysis with gradient shaving preparation. The polyimide film was treated with KOH. The imide ring opened through the alkaline treatment, and the amide structure and carboxylic acid salt were formed. The attainment depth of this structural change was almost proportional to the treatment time, and it reached about 8 μm after a 30‐min treatment. The degree of structural change through the alkaline treatment was almost constant after it reached a considerably degraded stage, and the chemically changed region penetrated into the inner part of the film from the surface. An intermediate layer before the final degraded stage appeared in the treated layer, and its thickness increased with the treatment time. The region that was changed chemically by the alkaline treatment progressed to the inner part simultaneously and continuously as the treatment time increased. The combined use of gradient shaving preparation and micro FTIR‐ATR line analysis was found to be extremely effective for the depth profiling of organic materials. © 2003 Wiley Periodicals, Inc. J Polym Sci Part B: Polym Phys 41: 2071–2078, 2003     

Dynamic mechanical thermal analysis transitions of partially and fully substituted cellulose fatty esters

The main transitions of cellulose fatty esters with different degrees of substitution (DSs) were investigated with dynamic mechanical thermal analysis. Two distinct main relaxations were observed in partially substituted cellulose esters (PSCEs). They were attributed to the glass‐transition temperature and to the chain local motion of the aliphatic substituents. The temperatures of both transitions decreased when DS or the number of carbon atoms (n) of the acyl substituent increased. Conversely, all the transitions of fully substituted cellulose esters occurred within a narrow temperature range, and they did not vary significantly with n. This phenomenon was explained by the formation of a crystalline phase of the fatty substituents. The presence of few residual OH groups in PSCEs was responsible for a large increase in the storage bending modulus, and it eliminated the effect of n on damping. © 2002 Wiley Periodicals, Inc. J Polym Sci Part B: Polym Phys 41: 281–288, 2003     

Concerning seven and eight mutually orthogonal Latin squares

In this paper, three new direct Mutually Orthogonal Latin Squares (MOLS) constructions are presented for 7 MOLS(24), 7 MOLS(75) and 8 MOLS(36); then using recursive methods, several new constructions for 7 and 8 MOLS are obtained. These reduce the largest value for which 7 MOLS are unknown from 780 to 570, and the largest odd value for which 8 MOLS are unknown from 1935 to 419. © 2003 Wiley Periodicals, Inc.     

Memory and a priori best strategy in complex adaptive systems

We employ an agent‐based model to show that memory and the absence of an a priori best strategy are sufficient for self‐segregation and clustering to emerge in a complex adaptive system with discrete agents that do not compete over a limited resource nor contend in a winner‐take‐all scenario. An agent starts from a corner of a two‐dimensional lattice and aims to reach a randomly selected site in the opposite side within the shortest possible time. The agent is isolated during the course of its journey and does not interact with other agents. Time‐bound obstacles appear at random lattice locations and the agent must decide whether to challenge or evade any obstacle blocking its path. The agent is capable of adapting a strategy in dealing with an obstacle. We analyze the dependence of strategy‐retention time with strategy for both memory‐based and memory‐less agents. We derive the equality spectrum to establish the environmental conditions that favor the existence of an a priori best strategy. We found that memory‐less agents do not polarize into two opposite strategy‐retention time distributions nor cluster toward a center distribution. © 2004 Wiley Periodicals, Inc. Complexity 9: 41–46, 2004     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003     

Transition‐metal‐catalyzed reactions of 5‐methylene‐2‐oxazolidinone and 5‐methylene‐1,3‐thiazolidine‐2‐thione with isocyanates

5‐Methylene‐2‐oxazolidinone (1) and 5‐methylene‐1,3‐thiazolidine‐2‐thione (4) react with various isocyanates to give the corresponding urethanes 3 and 5 in high yields in the presence of palladium(0) or palladium(II) catalyst under mild reaction conditions. A mechanism is proposed. Copyright © 2003 John Wiley & Sons, Ltd.