bluuebunny/crossref_metadata_2025 huggingface dataset:
The size Ramsey number of trees with bounded degree
Authors: Ke Xin
Published: May 2007

The size Ramsey number r̂(G, H) of graphs G and H is the smallest integer r̂ such that there is a graph F with r̂ edges and if the edge set of F is red‐blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r̂(Tnd, Tnd) ⩽ c · d2 · n and c · n3 ⩽ r̂(Kn, Tnd) ⩽ c(d)·n3 log n for every tree Tnd on n vertices. and maximal degree at most d and a complete graph Kn on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.
Searching for losers
Authors: Grabner Peter J.
Published: May 2007

We investigate the following process: N people select b losers by flipping coins. The 0‐party continues until there are less than b losers; then the 1‐party has to find the other losers by the same process. The average time for this process is about long2 N, but this result requires rather advanced methods. Furthermore, the average size of a binary tree associated to this process and the average number of coin flippings are computed. The method used in this article can be used to give asympotical solutions of a special type of bivariate recurrences. © 1993 John Wiley & Sons, Inc.
Efficient generation of random nonsingular matrices
Authors: Randall Dana
Published: May 2007

We present an efficient algorithm for generating an n × n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(n2), where M(n) is the time needed to multiply two n × n matrices, and the expected number of random bits it uses is n2 + 3. (Over other finite fields we use n2 + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n × n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have nonzero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant. © 1993 John Wiley & Sons, Inc.
The effect of random restrictions on formula size
Authors: Impagliazzo Russell , Nisan Noam
Published: May 2007

We consider the formula size complexity of boolean functions over the base consisting of ∧, ∨, and ¬ gates. In 1961 Subbotovskaya proved that, for any boolean function on n variables, setting all but a randomly chosen ϵn variables to randomly chosen constants, reduces the expected complexity of the induced function by at least a factor. This fact was used by Subbotovskaya to derive a lower bound of Ω(n1.5) for the formula size of the parity function, and more recently by Andreev who exhibited at lower bound of ΩC(n2.5/logO(1)(n)) for a function in P. We present the first improvement of Subbotovskaya's result, showing that the expected formual complexity of a function restricted as above is at most an O(ϵγ) franction of its original complexity, for

magnified image

This allows us to give an improved lower bound of Ω(n2.556…) for Andreev's function. At the time of discovery, this was the best formula lower bound known for any function in NP. © 1993 John Wiley & Sons, Inc.
On boolean decision trees with faulty nodes
Authors: Kenyon Claire , King Valerie
Published: May 2007

We consider the problem of computing with faulty components in the context of the Boolean decision tree model, in which cost is measured by the number of input bits queried, and the responses to queries are faulty with a fixed probability. We show that iffcan be represented ink‐DNF form and inj‐CNF form, thenO(nlog(min(k, j)/q)) queries suffice to computefwith error probability less thanq, wherenis the number of input bits. © 1994 John Wiley & Sons, Inc.
An upper bound for the solvability probability of a random stable roommates instance
Authors: Pittel Boris G. , Irving Robert W.
Published: May 2007

It is well‐known that not all instances of the stable roommates problem admit a stable matching. Here we establish the first nontrivial upper bound on the limiting behavior of Pn, the probability that a random roommates instance of size n has a stable matching, namely, limn→∞ Pn⩽ e1/2/2 (=0.8244…). © 1994 John Wiley & Sons, Inc.
Trie size in a dynamic list structure
Authors: Louchard G.
Published: May 2007

This article considers a classical binary tree implementation of a set of keys: the trie. The trie size properties in a static environment are well known: The size is asymptotically Gaussian when the number of keys is large. In this article we analyze the trie in a dynamic environment, where the trie is allowed to grow and shrink in a probabilistic way. It appears that the trie size can be described by a stochastic process which is asymptotically Gaussian non‐Markovian. This also allows the complete asymptotic analysis of the trie size maximum and the trie size integrated cost. © 1994 John Wiley & Sons, Inc.
On the number of cycles of given length of a free word in several random permutations
Authors: Nica Alexandru
Published: May 2007

Let w ≠ 1 be a free word in the symbols g1,…, gk and their inverses (i.e., an element of the free group Fk). For any s1,…, sk, in the group sn of all permutation of n objects, we denote by w(s1,…,sk) ϵ Sn the permutation obtained by replacing g1,…, gk with s1,…, sk in the expression of w. Let X (s1,…, sk) denote the number of cycles of length L of w(s1,…, sk). For fixed w and L, we show that X, viewed as a random variable on Snk, has (for n →∞) a Poisson‐type limit distribution, which can be computed precisely. © 1994 John Wiley & Sons, Inc.
On the genus of a random graph
Authors: Rödl Vojtěch , Thomas Robin
Published: May 2007

Let p = p(n) be a function of n with 0
 1 we were unable to compute this function.
Random I‐colorable graphs
Authors: Prömel Hans Jürgen , Steger Angelika
Published: May 2007

In this article we investigate properties of the class of all l‐colorable graphs on n vertices, where l = l(n) may depend on n. Let Gln denote a uniformly chosen element of this class, i.e., a random l‐colorable graph. For a random graph Gln we study in particular the property of being uniquely l‐colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l‐colorable graphs on n vertices with m = m(n) edges.
Constructions of permutation arrays for certain scheduling cost measures
Authors: Naor Joseph , Roth Ron M.
Published: May 2007

Constructions of permutation arrays are presented that are optimal or nearly‐optimal with respect to two cost measures: the so‐called longest‐jump measure and the longest‐monotone‐greedy‐subsequence measure. These measures arise in the context of scheduling problems in asynchronous, shared memory, multiprocessor machines.
A tight upper bound on the cover time for random walks on graphs
Authors: Feige Uriel
Published: May 2007

We prove that the expected time for a random walk to visit all n vertices of a connected graph is at most 4/27n3 + o(n3).
Randomized greedy matching. II
Authors: Aronson Jonathan , Dyer Martin , Frieze Alan , Suen Stephen
Published: May 2007

We consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V, E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge {u, v} to M and delete vertices u, v from G along with any vertices that become isolated. Our main result is that there exists a positive constant ϵ such that the expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + ϵ. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs.
On the Monte carlo boolean decision tree complexity of read‐once formulae
Authors: Santha Miklos
Published: May 2007

In the boolean decision tree model there is at least a linear gap between the Monte Carlo and the Las Vegas complexity of a function depending on the error probability. We prove for a large class of read‐once formulae that this trivial speed‐up is the best that a Monte Carlo algorithm can achieve. For every formulaFbelonging to that class we show that the Monte Carlo complexity ofFwith two‐sided errorpis (1 − 2p)R(F), and with one‐sided errorpis (1 −p)R(F), whereR(F) denotes the Las Vegas complexity ofF. The result follows from a general lower bound that we derive on the Monte Carlo complexity of these formulae. This bound is analogous to the lower bound due to Saks and Wigderson on their Las Vegas complexity.
Large antichains in the partition lattice
Authors: Canfield E. R. , Harper L. H.
Published: May 2007

Consider the partially ordered set of all partitions of an n‐element set, ordered by refinement. The sizes of the various ranks within this poset are the Stirling numbers of the second kind. We show that the ratio of the size of the largest antichain to the size of the largest rank exceeds n1/35 for all n sufficiently large.
A passage time for greedy‐coloring cycles
Authors: Preater J.
Published: May 2007

We consider the progress of the greedy vertex coloring algorithm applied to cycle graphs. In particular we study the asymptotic distribution of the number of vertices colored by the algorithm when the third color is first used (if it is).
Fractional products of sets
Authors: Blei Ron , Peres Yuval , Schmerl James
Published: May 2007

For integers d > 1 and arbitrary 1 ⩽ α ⩽ d, α‐products in d‐fold Cartesian products are produced by probabilistic methods. Some explicit constructions are given by solutions of instances of the Turán problem for graphs.
Convergence in homogeneous random graphs
Authors: Łuczak Tomasz , Shelah Saharon
Published: May 2007

For a sequence p̄ = (p(1), p(2), ‥ .), let G(n, p̄) denote the random graph with vertex set {1, 2, ‥ ., n} in which two vertices i, j are adjacent with probability p(|i − j|), independently for each pair. We study how the convergence of probabilities of first order properties of G(n, p̄), can be affected by the behaviour of p̄ and the strength of the language we use.
Geometric algorithms for the minimum cost assignment problem
Authors: Tokuyama Takeshi , Nakano Jun
Published: May 2007

We consider the minimum‐cost λ‐assignment problem, which is equivalent to the minimum‐weight one‐to‐many matching problem on a complete bipartite graph Γ = (A, B), where A and B have n and k nodes (n ⩾ k), respectively. Formulating the problem geometrically, we given an O(kn + k2.5n0.5 log1.5 n) time randomized algorithm, which is better than the existing O(kn2 + n2 log n) time algorithm if n > k log k.
Improved boolean formulas for the Ramsey graphs
Authors: Savický Petr
Published: May 2007

In the theory of the random graphs, there are properties of graphs such that almost all graphs satisfy the property, but there is no effective way to find examples of such graphs. By the well‐known results of Razborov, for some of these properties, e.g., some Ramsey property, there are Boolean formulas in ACC representing the graphs satisfying the property and having exponential number of vertices with respect to the number of variables of the formula. Razborov's proof is based on a probabilistic distribution on formulas of n variables of size approximately nd2 log d, where d is a polynomial in n, and depth 3 in the basis { ∧, ⊕} with the following property: The restriction of the formula randomly chosen from the distribution to any subset A of the Boolean cube {0, 1}n of size at most d has almost uniform distribution on the functions A → {0, 1}. We show a modified probabilistic distribution on Boolean formulas which is defined on formulas of size at most nd log2 d and has the same property of the restrictions to sets of size at most d as the original one. This allows us to obtain formulas the complexity of which is a polynomial of a smaller degree in n than in Razborov's paper while the represented graphs satisfy the same properties.
On an anti‐Ramsey property of Ramanujan graphs
Authors: Haxell P. E. , Kohayakawa Y.
Published: May 2007

If G and H are graphs, we write G→ H (respectively, G→ TH) if for any proper edge‐coloring γ of G there is a subgraph H' ⊂ G of G isomorphic to H (respectively, isomorphic to a subdivision of H) such that γ is injective on E(H'). Let us write Cl for the cycle of length l. Spencer (cf. Erdös 10]) asked whether for any g ⩾ 3 there is a graph G = Gg such that (i) G has girth g(G) at least g and (ii) G→ TC3. Recently, Rödl and Tuza [22] answered this question in the affirmative by proving, using nonconstructive methods, a result that implies that, for any t ⩾ 1, there is a graph G = Gt of girth t + 2 such that G→ C2t+2. In particular, condition (ii) may be strengthened to (iii) G→ C𝓁 for some l = 𝓁(G). For G = Gt above 𝓁 = 𝓁(G) = 2t + 2 = 2g(G) − 2. Here, we show that suitable Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak [18] are explicit examples of graphs G = Gg satisfying (i) and (iii) above. For such graphs, 𝓁 = l(G) in (iii) may be taken to be roughly equal to (3/2)g(G), thus considerably improving the value 2g(G) − 2 given in the result of Rödl and Tuza. It is not known whether there are graphs G of arbitrarily large girth for which (iii) holds with 𝓁 = 𝓁(G) = g(G).
Upper bounds for the expected length of a longest common subsequence of two binary sequences
Authors: Dančík Vlado , Paterson Mike
Published: May 2007

Let f(n) be the expected length of a longest common subsequence of two random binary sequences of length n. It is known that the limit γ = limn→ ∞ n−1 f(n) exists. Improved upper bounds for γ are given using a new method.
Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
Authors: Alon Noga , Frieze Alan , Welsh Dominic
Published: May 2007

The Tutte‐Gröthendieck polynomial T(G; x, y) of a graph G encodes numerous interesting combinatorial quantities associated with the graph. Its evaluation in various points in the (x, y) plane give the number of spanning forests of the graph, the number of its strongly connected orientations, the number of its proper k‐colorings, the (all terminal) reliability probability of the graph, and various other invariants the exact computation of each of which is well known to be #P‐hard. Here we develop a general technique that supplies fully polynomial randomised approximation schemes for approximating the value of T(G; x, y) for any dense graph G, that is, any graph on n vertices whose minimum.
The strong convergence of maximal degrees in uniform random recursive trees and dags
Authors: Devroye Luc , Lu Jiang
Published: May 2007

We show that the maximal degree in a uniform random recursive tree is almost surely (1 + o(1)) log2n. A random directed acyclic graph on n nodes is defined by connecting the ith node for each i > m with r of its predecessors uniformly and at random. The maximal degree is shown to be almost surely (1 + o(1))log1+1/rn.
An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
Authors: Krajíček Jan , Pudlák Pavel , Woods Alan
Published: May 2007

We prove lower bounds of the form exp(nε d), εd > 0, on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth d, for any constant d. This is the largest lower bound for the strongest proof system, for which any superpolynomial lower bounds are known.
Perfect matchings in random s‐uniform hypergraphs
Authors: Frieze Alan , Janson Svante
Published: May 2007

Let E = {X1, X2…, Xm} where the Xi ⊆ V for 1 ≤ i ≤ m are distinct. The hypergraph G = (V, E) is said to be s‐uniform if |X1| = s for 1 ≤ i ≤ m. A set of edges M = {Xi : i ϵ I} is a perfect matching if (i) i ≠ j ϵ I implies Xi ∩ Xi = 0, and (ii) ∪iϵI Xi = V.

In this article we consider the question of whether a random s‐uniform hypergraph contains a perfect matching. Let s ≥ 3 be fixed and m/n4/3 → ∞. We show that an s‐uniform hypergraph with m edges chosen uniformly from [74] contains a perfect matching with high probability. This improves an earlier result of Schmidt and Shamir who showed that m/n3/2 → ∞ suffices. © 1995 John Wiley & Sons, Inc.
Tail bounds for occupancy and the satisfiability threshold conjecture
Authors: Kamath Anil , Motwani Rajeev , Palem Krishna , Spirakis Paul
Published: May 2007

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well‐known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3‐SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c* ≈︁ 4.2. We provide a strong upper bound on the value of c*, showing that for c > 4.758 a random 3‐SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds.
The variance of a partial match retrieval in a multidimensional symmetric trie
Authors: Schachinger Werner
Published: May 2007

Let N records be stored in an M‐dimensional trie (M‐d trie). It is shown that under the symmetric Bernoulli model the variance of the cost CNω of a partial match retrieval is magnified image with continuous periodic function τω, where u is the number of unspecified components in a query ω of size M. This confirms in quantitative manner a conjecture by Kirschenhofer, Prodinger, and Szpankowski [Int. J. Found. Comput. Sci., 4, 69–84 (1993)], who presented a detailed analysis of Var CNω in the M = 2, u = 1‐case, but used in their proof a transformation formula of Ramanujan, which does not seem to have an analogue for M > 2. Our analysis is based on exponential approximations and Mellin inversion.
Bounded branching process and and/or tree evaluation
Authors: Karp Richard M. , Zhang Yanjun
Published: May 2007

We study the tail distribution of supercritical branching processes for which the number of offspring of an element is bounded. Given a supercritical branching process {Zn} with a bounded offspring distribution, we derive a tight bound, decaying super‐exponentially fast as c increases, on the probability Pr[Zn > cE(Zn)], and a similar bound on the probability Pr[Zn ≤ E(Zn)/c] under the assumption that each element generates at least two offspring. As an application, we observe that the execution of a canonical algorithm for evaluating uniform AND/OR trees in certain probabilistic models can be viewed as a two‐type supercritical branching process with bounded offspring, and show that the execution time of this algorithm is likely to concentrate around its expectation, with a standard deviation of the same order as the expectation.
Hypergeometrics and the cost structure of quadtrees
Authors: Flajolet Philippe , Labelle Gilbert , Laforest Louise , Salvy Bruno
Published: May 2007

Several characteristic parameters of randomly grown quadtrees of any dimension are analyzed. Additive parameters have expectations whose generating functions are expressible in terms of generalized hypergeometric functions. A complex asymptotic process based on singularity analysis and integral representations akin to Mellin transforms leads to explicit values for various structure constants related to path length, retrieval costs, and storage occupation.
A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
Authors: Jerrum Mark
Published: May 2007

A fully polynomial randomized approximation scheme is presented for estimating the number of (vertex) k‐colorings of a graph of maximum degree Δ, when k ≥ 2Δ + 1. © 1995 John Wiley & Sons, Inc.
Asymptotic packing via a branching process
Authors: Spencer Joel
Published: May 2007

It is shown that under certain side conditions the natural random greedy algorithm almost always provides an asymptotically optimal packing of disjoint hyperedges from a hypergraph H.
Asymptotic optimality of competitive associative nets and its application to incremental learning of nonlinear functions
Authors: Kurogi Shuichi
Published: May 2007

The competitive associative net CAN2 is a neural net that provides piecewise‐linear approximation through incremental learning of a nonlinear function by the associative net function. The effectiveness of this net has already been shown by applications to function approximation, control, precipitation estimation, and other problems. The learning algorithm essentially includes competitive learning based on the gradient method and suffers from the local solution problem. The purpose of this paper is to circumvent this problem. First, the asymptotic optimality condition, that is, the optimality condition for minimizing the mean‐square error of the approximation function, is derived for the case in which the net is composed of a very large number of units. This condition can be used to decide whether the weight assignment each time is close to the optimal solution, and also to suggest weight assignments closer to the optimal solution. The condition is incorporated into a learning algorithm based on the gradient method, resulting in the following learning algorithm: when it is decided that the weight assignment obtained by the gradient method is not close to the optimal solution, the weights of some units are reinitialized so that the weight assignment is closer to the optimal solution. Finally, numerical experiments are performed in which the proposed learning algorithm is applied to several benchmark functions. The effectiveness of the proposed algorithm is verified. The results are compared to the results of experiments by BPN (Back‐Propagation Net), RBFN (Radial Basis Function Net), and SVR (Support Vector Regression), and it is shown that CAN2 based on the proposed algorithm has excellent function approximation performance. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(9): 85–96, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10538
A competitive information recommendation system and its rational recommendation method
Authors: Sakamoto Toshiki , Kitamura Yasuhiko , Tatsumi Shoji
Published: May 2007

Retrieval engines are widely used as a means for users to acquire information satisfying their requirements from the large amount of diversified Web information on the Internet. However, retrieval engines cannot be useful unless the requirements from the user are explicitly represented in terms of keywords. Consequently, information recommendation systems are attracting attention as a means of providing information which is likely to interest the user. This paper proposes a competitive information recommendation system, which recommends information to the user by competitive interaction of multiple agents, each having an individual character, with the user. In the competitive information recommendation system, if the agent simply recommends the information autonomously, information desired by the user may not be recommended, or many interactions may be needed before the user acquires the desired information. Therefore, this paper proposes a rational recommendation method in which the utility for the user that can be obtained from the recommended information is represented by a multi‐attribute utility function, and the agent recommends only information desirable to the user while learning the weight for each attribute. Then the best profit strategy, in which the profit of the agent has priority, and the best learning strategy, in which learning of the utility to the user has priority, are presented as information recommendation strategies for the agent. An evaluation experiment shows that the best profit strategy is better. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(9): 74–84, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10662
Generation of threshold functions of high‐order satisfying monotonicities
Authors: Kamada Yukihiro , Miyasaki Kiyonori
Published: May 2007

This paper presents a generation procedure for high‐order threshold functions, considering the high‐order neighbor vector and the monotonic property. Specifically, it is first shown that the high‐order neighbor vector can be derived from an input vector which is noncomparable by the high‐order threshold function. Then, it is shown that a monotonic function of a high‐order variable can easily be generated from the given monotonic function. Based on the generation process for the monotonic function, the generation procedure for high‐order threshold functions is derived. It is also shown that if a given high‐order threshold function preserves monotonicity, the generated high‐order threshold function also preserves monotonicity, and also the high‐order terms. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(9): 63–73, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20243
Bayesian classification of a human custom based on stochastic context‐free grammar
Authors: Mitomi Humikazu , Fujiwara Fuyuki , Yamamoto Masanobu , Sato Taisuke
Published: May 2007

This paper describes a new approach for gesture recognition based on stochastic context‐free grammar (SCFG). We focus on the actions in the Japanese tea ceremony, where structure of the action can be described by context‐free grammar. Our aim is to recognize the actions in the tea ceremony. Existing SCFG approach consists of generating symbol stream, parsing, and recognition. The symbol stream often includes uncertainty. Therefore, the parsing process needs to recover from errors in the entry process. This paper proposes an error‐free approach to segment an action into a set of events. This approach, based on acceleration of body motion, can produce events corresponding to a terminal symbol with little error. After translating the events into a set of symbol streams, parsing the set of the streams leaves a small number to be derived. The number of potential streams is not too large since each event is correctly segmented. Among the remaining streams, our SCFG can identify the action with a maximum posterior probability. Giving an SCFG rule the multiple probabilities, one SCFG can recognize multiple actions. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(9): 52–62, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20531
Spoken language understanding method using confidence measure and dialogue history
Authors: Fujiwara Noriki , Itoh Toshihiko , Araki Kenji , Kai Atsuhiko , Konishi Tatsuhiro , Itoh Yukihiro
Published: May 2007

In the real environment, it is hard for a speech recognizer to avoid misrecognitions completely. However, if misrecognitions occur, user's intentions are usually misunderstood by a conventional language understanding technique, which simply gives priority to the higher rank hypothesis of a speech recognition result (N‐best). The utterances in a dialogue are coherent and correct user's intentions might appear in the lower rank hypothesis of N‐best. To understand user's speech intentions in the real environment, we propose the language understanding technique that utilizes the dialogue context and confidence measure, which is the word posterior probability. The experimental results show that proposed technique is more efficient (about 15%) than the conventional technique. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(9): 21– 31, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20758
High‐speed processing and high‐reliability technology in an integrated fixed‐line and wireless, autonomous decentralized IC card system
Authors: Shiibashi Akio
Published: May 2007

Increasing the processing speed of automatic fare collection gates (AFCG) is a topic of great importance for supporting passengers who are getting on and off high‐density transportation at peak hours. On the other hand, reliability is indispensable for processing tickets, which are a type of noncurrency negotiable instrument. Therefore, a passenger ticket system that provides both high‐speed processing and high reliability is required. To increase passenger convenience and reduce maintenance costs, a wireless IC card ticket system is desirable. However, since this system uses wireless communication for processing that is carried out with the fare collection gates, the drop in data during ticket examination is a problem. In this paper, the author proposes an autonomous decentralized technology for satisfying the requirements of high‐speed processing and high reliability in a wireless IC card ticket system. IC cards, automatic fare collection gates, and a central server are designed as nodes of an autonomous decentralized system. In particular, to achieve high‐speed processing, the author proposes an autonomous decentralized algorithm for fare calculation by IC cards and automatic fare collection gates. To prove the effectiveness of this algorithm, the author creates models and performs comparison tests. Also, as a technology for ensuring high reliability, the author proposes an autonomous decentralized data consistency technology for each subsystem. These technologies were introduced in the Suica system (East Japan Railway Company) in Japan and their effectiveness was proven. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(9): 1–10, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20800
Cure rate model with interval censored data
Authors: Kim Yang‐Jin , Jhun Myoungshic
Published: May 2007

In cancer trials, a significant fraction of patients can be cured, that is, the disease is completely eliminated, so that it never recurs. In general, treatments are developed to both increase the patients' chances of being cured and prolong the survival time among non‐cured patients. A cure rate model represents a combination of cure fraction and survival model, and can be applied to many clinical studies over several types of cancer. In this article, the cure rate model is considered in the interval censored data composed of two time points, which include the event time of interest. Interval censored data commonly occur in the studies of diseases that often progress without symptoms, requiring clinical evaluation for detection (Encyclopedia of Biostatistics. Wiley: New York, 1998; 2090–2095). In our study, an approximate likelihood approach suggested by Goetghebeur and Ryan (Biometrics2000;56:1139–1144) is used to derive the likelihood in interval censored data. In addition, a frailty model is introduced to characterize the association between the cure fraction and survival model. In particular, the positive association between the cure fraction and the survival time is incorporated by imposing a common normal frailty effect. The EM algorithm is used to estimate parameters and a multiple imputation based on the profile likelihood is adopted for variance estimation. The approach is applied to the smoking cessation study in which the event of interest is a smoking relapse and several covariates including an intensive care treatment are evaluated to be effective for both the occurrence of relapse and the non‐smoking duration. Copyright © 2007 John Wiley & Sons, Ltd.
Cognitive radio realities
Authors: Le Bin , Rondeau Thomas W. , Bostian Charles W.
Published: May 2007

A cognitive radio (CR) is a transceiver that is aware, adaptive, and capable of learning. It may be visualized and realized as an intelligent software package (cognitive engine) controlling a software defined radio platform. The cognitive engine executes a set of nested loops constituting a cognition cycle, drawing on experience and stored knowledge to optimize a set of user‐chosen quality of service measures. The process relies on the effectiveness of a set of tools that are individually well known but rarely found together: multi‐objective genetic algorithms, case‐based decision theory, and neural networks. Practical implementation problems include passing environmental information from the radio to the cognitive engine, acting on that information, and performing real‐time control of the radio platform by the cognitive engine. In this paper, we discuss our approach to developing and implementing a CR. Copyright © 2007 John Wiley & Sons, Ltd.
Spectrum sensing in cognitive radio networks: the cooperation‐processing tradeoff
Authors: Ghasemi Amir , Sousa Elvino S.
Published: May 2007

Opportunistic unlicensed access to the (temporarily) unused frequency bands across the licensed radio spectrum is currently being investigated as a means to mitigate the spectrum scarcity. Such opportunistic access calls for the implementation of safeguards so that the ongoing licensed operations are not interfered with. Among different candidates, sensing‐based access, where thesecondary(unlicensed) users transmit if they sense theprimary(licensed) band to be free, is particularly appealing due to its low deployment cost and its compatibility with legacy primary systems. Incorporatingspectral awarenessfunctionality into the radio transceivers is a major step towards the realization of thecognitive radios. In this paper performance of spectrum‐sensing cognitive radios is studied under channel fading. In particular, it is shown that due to the uncertainty resulting from fading, local signal processing alone may be inadequate to meet the performance requirements. To remedy this issue, cooperation among secondary users is proposed and studied in this paper. Moreover, we characterize and study a tradeoff between local processing and cooperation, which should be balanced in order to maximize the spectrum utilization. Copyright © 2007 John Wiley & Sons, Ltd.
Spectrum sharing through distributed coordination in dynamic spectrum access networks
Authors: Zhao Jun , Zheng Haitao , Yang Guang‐Hua
Published: May 2007

Spectrum sharing in Open Spectrum systems is a challenging problem, particularly since users experience dynamic spectrum availabilities that vary over time and location. In the absence of any centralized infrastructure, users coordinate their spectrum usage to support fair access of spectrum and avoid interference. One critical challenge is to construct an efficient signaling path in the presence of spectrum dynamics, where users exchange control and negotiation information reliably. In this paper, we propose a distributed coordination protocol (HD‐MAC) to construct an in‐band control path, without relying on the existence of a pre‐assigned out‐of‐band control channel. In particular, we propose a distributed group formation to construct coordination path using local common channels, and a heterogeneity‐aware ranking scheme to select channels for data transmissions. Extensive experimental results demonstrate the efficiency and reliability of the proposed approach. Copyright © 2007 John Wiley & Sons, Ltd.
Automatic antenna‐tuning unit for software‐defined and cognitive radio
Authors: Oh Sung‐Hoon , Song Hang , Aberle James T. , Bakkaloglu Bertan , Chakrabarti Chaitali
Published: May 2007

This paper discusses the implementation of an automatic antenna tuning unit system (ATU) for software‐defined and cognitive radio. The ATU simplifies radio frequency (RF) front‐end design for multi‐band, multi‐mode radios by allowing an electrically small reconfigurable antenna to become a frequency‐agile selective component (essentially a tunable filter). In implementing the ATU, impedance synthesizers (tunable matching networks) using RF MEMS switches as the control elements are used to match a more or less arbitrary load to a convenient impedance value. To generate feedback data that can be used to optimize the impedance synthesizer, the incident and reflected powers at the input to the impedance synthesizer are sampled using a power sensor block comprising directional coupler, logarithmic RF power detectors, analog‐to‐digital converters (ADCS), and return loss computation algorithms running on a field programmable gate array (FPGA). From a practical point of view, in order to be compatible with commercial wireless handset devices, we propose to design and ultimately implement a fully integrated ATU system. In this paper, a hard‐ ware implementation of the ATU prototype has been demonstrated to verify narrowband automatic tuning ability of the ATU under constantly changing environment conditions, and we present simulated results for a logarithmic power detector designed with 55 dB dynamic range over the 800 MHz–2 GHz frequency band using 0.25 µ CMOS technology. Copyright © 2007 John Wiley & Sons, Ltd.
DSP implementation of a bit loading algorithm for adaptive wireless multicarrier transceivers
Authors: Cudnoch Martin , Wyglinski Alexander M. , Labeau Fabrice
Published: May 2007

In this paper, we present a proof‐of‐concept, fixed‐point, DSP hardware implementation of an adaptive bit loading algorithm that is designed for wireless multicarrier transceivers. Adaptive bit loading is used to enhance the performance of multicarrier transceivers by tailoring the subcarrier signal constellations to the channel conditions, which can vary across the subcarriers. Since most bit loading algorithms possess a high computational cost and are unable to cope with rapid variations of wireless channels, they are seldom used in present wireless standards. To prove that adaptive bit loading is feasible for wireless transceivers, our work focuses on the implementation of a known bit loading algorithm that can quickly search for the final bit allocation in an iterative manner. The goal of this algorithm is to yield the largest‐possible throughput while satisfying a mean BER constraint. The performance of the hardware implementation operating in time‐varying channel conditions is studied in terms of the overall throughput. Furthermore, the robustness of the hardware implementation is evaluated, relative to sudden changes in the channel that interrupts the run of the algorithm. Real‐time operations and fixed‐point representation issues are included in the discussion. Additionally, we propose a modified algorithm implementation that is more robust to channel variations. Copyright © 2007 John Wiley & Sons, Ltd.
Cognitive engine implementation for wireless multicarrier transceivers
Authors: Newman Tim R. , Barker Brett A. , Wyglinski Alexander M. , Agah Arvin , Evans Joseph B. , Minden Gary J.
Published: May 2007

This paper presents a genetic‐algorithm driven, cognitive radio decision engine that determines the optimal radio transmission parameters for single and multicarrier systems. Determining the appropriate radio parameters, given a dynamic wireless channel environment is the primary feature of cognitive radios for wireless communication systems. Genetic algorithms (GAs) are designed to select the optimal transmission parameters by scoring a subset of parameters and evolving them until the optimal value is reached for a given goal. Although there have been implementations of GA‐based single carrier cognitive radio engines, the performance of these algorithms has not been thoroughly analyzed nor have the fitness functions employed by the algorithms been explored in detail. Multicarrier systems are common in today's communication environment, thus cognitive techniques that account for only single‐carrier systems neglect the practical issues of multiple carriers. A set of accurate single carrier and multicarrier fitness functions for our GA implementation that completely control the evolution of the algorithm have been derived. The performance analysis results illustrate the trade‐offs between the convergence time of the GA and the size of the GA search space. Copyright © 2007 John Wiley & Sons, Ltd.
Constitutive Equations, Stability and Bifurcation of Elastoplastic Structures
Authors: Germain P.
Published: May 2007

This review paper gives a uniform presentation of some recent results on the. stability of elastic plastic structures. It starts by recalling a general method to write constitutive equations in finite deformations with the introduction of an internat variable– generally a matrix – which describes the modification of material properties. First, this formulation is shown to be quite convenient to study cracks and their evolution under a varying load for brittle or ductile materials. Then, a quite general method for the treatment of the stability and bifurcations of equilibrium of an elastic plastic structure is presented and applied to some simple examples. The results already published in the literature are recovered.
Globales Verhalten erzwungener nichtlinearer Schwingungen und Einsetzen von Chaos
Authors: Schmidt G.
Published: May 2007

Das globale, mit dem Einsetzen chaotischer Bewegungen verbundene Verhalten erzwungener nichtlinearer Schwingungen wird für verschiedene Formen der Duffing‐Gleichung, speziell für die von P. Holmes untersuchte Gleichung und die Pendelgleichung diskutiert. Der Vorteil der Erregungskurven, die die Resonanzamplituden in Abhängigkeit von den Erregungsamplituden bestimmen, und ihre Beziehung zu den Resonanzkurven werden gezeigt.
Internal Resonances in Weakly Nonlinearly Coupled Oscillators with Slowly Varying Parameters
Authors: Shivamoggi B. K.
Published: May 2007

The present paper considers the problem of internal resonances in a system of two linear oscillators which are weakly nonlinearly coupled. The system parameters such as the uncoupled frequencies of the oscillators vary slowly in time so that internal resonances prevail only temporarily. One issue of interest in such problems is how the presence of nonlinear coupling affects the adiabatic invariance of the individual actions of the two oscillators. The purpose of this paper is to give a method to investigate this issue quite generally, without assuming special forms of temporal variations of the uncoupled frequencies of the two oscillators and without considering the details of the transition region corresponding to an internal resonance.
Magnetohydrodynamic Stability of Boundary Layer Flow with Suction or Injection along a Flat Plate
Authors: Watanabe T.
Published: May 2007

The flow of an incompressible electrically conducting fluid past, a semi‐infinite flat plate in the presence of a transverse magnetic field is studied considering the effect of uniform suction or injection. The transformed boundary layer equations are obtained, and the numerical calculations of resulting equations are performed for various values of magnetic parameter and suction or injection parameter. The neutral stability curves for wavelike disturbances of Tollmien‐Schlichting type are then presented for the velocity profiles obtained above. The results are given for the velocity profiles, coefficient of skin friction, displacement thickness and the critical Reynolds numbers.
Bendixon‐Type Theorems with Applications
Authors: Tóth J.
Published: May 2007

Bendixson's theorem on the nonexistence of periodic solutions of differential equations is generalized to the N ‐dimensional case. An application of the theorem in formal reaction kinetics is shown. Then a theorem analogous to Schneider's generalization is given. Finally, a theorem on implicit systems is formulated and applied to get a sufficient condition for the absence of periodic solutions in a generalized Liénard‐equation.
Lösung linearer Fredholmscher Integralgleichungen mit Kernen vom Greenschen Typ
Authors: Micke A.
Published: May 2007

Es wird eine Modifikation der Simpson‐ und der Simpsonschen‐3/8‐Formel vorgestellt, die es gestattet, Fredholmsche Integralgleichungen mit Kernen, die entlang der Diagonale s = t unstetig und entlang der Gerade s = a + b – t nicht differenzierbar sein können, mit einer Konvergenzordnung O(h4) aufzulösen. Zur Lösung der entstehenden linearen Gleichungssysteme wird eine iterative Variante des Nyström‐Verfahrens verwendet. Anhand von numerischen Beispielen erfolgt ein Vergleich mit anderen Quadraturverfahren.
Zur Konvergenz von Finite‐Elemente‐Näherungen elliptischer quasilinearer Differentialgleichungen bei geringer Regularität der Lösung
Authors: Kosler R.
Published: May 2007

Betrachtet werden nicht notwendig stark elliptische quasilineare Differentialgleichungen zweiter Ordnung in zwei Dimensionen. Unter schwachen Regularitätsbedingungen für die Lösung wird die Konvergenz der Methode der finiten Elemente für die Energienorm und für die Maximumnorm nachgewiesen.
Shock Formation Distance in a Two‐Dimensional Steady Supersonic Flow Over a Concave Corner in Radiative Magnetogasdynamics
Authors: Sharma V. D. , Shyam R. , Singh L. P.
Published: May 2007

Using the theory for the propagation of wavefronts defined by weak discontinuities, the paper presents an analysis of shock wave formation in a two‐dimensional steady supersonic flow over a concave corner in radiative magnetogasdynamics. Transport equations are derived which lead to the determination of the shock formation distance and also to conditions which ensure that no shock will ever evolve on the wave front. It is assessed as to how the shock formation distance is influenced by (i) the presence of radiative and magnetohydrodynamic effects, (ii) the initial curvature of the concave wall, and (iii) the upstream flow Mach number.
Crack Problem in a Transversely Isotropic Medium with a Penny‐Shaped Crack under Transient Thermal Loading
Authors: Ishida R.
Published: May 2007

In this paper, we deal with a theoretical approach to find stress intensity factors for transient thermal loading in an infinite transversely isotropic elastic medium with a penny‐shaped crack the surfaces of which are subjected to a sudden change of temperature. Variations of the stress intensity factors with time are calculated and illustrated in figures.
Über die Wirkung ungleichförmiger Dämpfung bei Kombinationsresonanzen zweiter Art
Authors: Füllekrug U. , Behr D.
Published: May 2007

Bei der Untersuchung der kinetischen Stabilität elastischer Systeme wird man auf rheolineare Differentialgleichungssysteme geführt. Wenn hierbei gewisse Beziehungen zwischen den Eigenfrequenzen und der Frequenz der Parametererregung bestehen, treten breite Instabilitätsgebiete mit unbeschränkt wachsenden Lösungen auf. In dem Instabilitätsbereich, der als Kombinationsresonanz zweiter Art und erster Ordnung bezeichnet wird, kann eine Zunahme der Dämpfung auch destabilisierend wirken. Zur genaueren Untersuchung dieses Phänomens wird ein einfaches parametererregtes Schwingungssystem betrachtet. Die Lösung der Bewegungsgleichungen erfolgt näherungsweise mit dem Verfahren der langsam veränderlichen Amplitude. Einen besonderen Aufschluß über das Stabilitätsverhalten gibt der Verlauf der charakteristischen Exponenten in der komplexen Ebene. Ist die Frequenzbeziehung für eine Kombinationsresonanz zweiter Art und erster Ordnung exakt erfüllt, dann hat jede Erhöhung der Dämpfung eine weitere Stabilisierung zur Folge. In der Nachbarschaft dieser Frequenzbeziehung gilt dies jedoch nicht mehr. Der Verlauf der charakteristischen Exponenten zeigt bei gleichförmiger Dämpfung einen charakteristisch anderen Verlauf als bei ungleichförmiger Dämpfung. Hiermit lassen sich der destabilisierende Einfluß ungleichförmiger Dämpfung und die niedrigeren Stabilitätsgrenzen erklären.
Die zweiparametrige Matrizeneigenwertaufgabe
Authors: Schneider J.
Published: May 2007

Die punktweise Lösung mehrparametriger Eigenwertaufgaben ist aufwendig und von nur geringem qualitativem Aussagewert. Dagegen ermöglicht die Kenntnis von Asymptoten, von Steigungen und Krümmungen in einigen Punkten sowie von Einschließungsgebieten der Eigenkurven einen schnelleren Überblick und erleichtert ihre rasche Konstruktion. Abgeleitet werden solche und ähnliche Hilfsaussagen sämtlich aus der charakteristischen Gleichung des Problems, deren explizite Aufstellung jedoch stets vermieden wird.