Asymptotic optimality of the GMD and Chase decoding algorithms

The generalized minimum distance (GMD) and Chase (1972) decoding algorithms are some of the most important suboptimum bounded distance decoding algorithms for binary linear block codes over an additive white Gaussian noise (AWGN) channel. We compute the limitation of the ratio between the probability of decoding error for the GMD or any one of the Chase decoding algorithms and that of the maximum-likelihood (ML) decoding when the signal-to-noise ratio (SNR) approaches infinity. If the minimum Hamming distance of the code is greater than 2, the limitation is shown to be equal to 1 and thus the GMD and Chase decoding algorithms are asymptotically optimum.     

Performance analysis of disk allocation method usingerror-correcting codes

The problem of distributing a Cartesian product file on multiple disks to maximize the parallelism for partial match queries is addressed. C. Faloutsos et al. (1989) have proposed an allocation method for Cartesian product files on multiple disks by using linear error-correcting codes. The performance of the allocation method is analyzed. Some conditions under which the allocation method is strictly optimal for queries with a given number of unspecified attributes are presented. A necessary and sufficient condition for a linear code to give a strictly optimal allocation method is discussed. Formulas for the average response time on queries with w unspecified attributes, denoted T_w, in terms of the weight distribution of the code or its dual code, and formulas for the average response time Ton all queries, are given. Several examples whose average response times T_w or T are close to theoretical lower bounds are presented     

Magnetic Field Measurement System in Superconducting Combined Function Magnets for the J-PARC Neutrino Beam Line

Magnetic field measurements have been performed for the first full-scale magnet system assembled with the cryostat for the J-PARC proton beam line of neutrino experiment. In the measurement system, the probe position with respect to magnet central axis is measured by a Helium Neon laser and a position sensitive detector, PSD, in order to obtain an exact dipole field strength. Errors associated with the PSD misalignment and influences on the PSD signals by the magnetic field were evaluated. The measured dipole components approached to the design values by compensating those with the probe position. The latest beam simulation indicated that the measured values of magnetic field were good enough for the primary proton beam transport.     

Decidable problems on the strong connectivity of Petri net reachability sets

For a Petri net N and a marking M, let R_N(M) be the set of markings reachable from M and let C_N(M) be the set of markings M′ such that M′ ?R_N(M) and M?R_N(M′)C_N(M) is a strongly connected component of R_N(M) to which M belongs. If R_N(M) = C_N (M), then N is said to be M-reversible, and if N is M-reversible for every marking M, then N is said to be reversible. In this paper the following results are presented. (1) C_N(M) is semilinear and therefore it is decidable whether (i) M′ ?C_N(M), (ii) C_N(M) is a finite set, (iii) C_N(M) ? C_N′(M′), and (iv) given two markings M and M′ such that M ? M′, there is a nonnegative integer k such that M + k(M ? M′) ?R_N(M′). (2) It is decidable whether (i) N is M-reversible or not, and (ii) N is reversible or not. (3) Given a Petri net N and a marking M, we can construct an M-reversible Petri net N′ such that C_N(M) = R_N′(M). (4) The equality problem for the sets of all firing sequences of an M-reversible Petri net N and an M′-reversible Petri net N′ is decidable. And some related problems are discussed.     

Membership problems for data dependencies in relational expressions

In relational databases, a query can be formulated in terms of a relational algebra expression using projection, selection, restriction, cross product and union. In this paper, we consider a problem, called the membership problem, of determining whether a given dependency d is valid in a given relational expression E over a given database scheme R that is, whether every instance of the view scheme defined by E satisfies d (assuming that the underlying constraints in R are always satisfied).Consider the case where each relation scheme in R is associated with functional dependencies (FDs) as constraints, and d is an FD. Then the complement of the membership problem is NP-complete. However, if E contains no union, then the membership problem can be solved in polynomial time. Furthermore, if E contains neither a union nor a projection, then we can construct in polynomial time a cover for valid FDs in E, that is, a set of FDs which implies every valid FD in E.Consider the case where each relation scheme in R is associated with multivalued dependencies (MVDs) as well as FDs, and d is an FD or an MVD. Even if E consists of selections and cross products only, the membership problem is NP-hard. However, if E contains no union, and each relation scheme name in R occurs in E at most once, then the membership problem can be solved in polynomial time. As a corollary of this result, it can be determined in polynomial time whether a given FD or MVD is valid in $\text{R}{}_1\text{???R}{}_{\mathrm{s}}$, where R₁,…,R_s are relation schemes with FDs and MVDs, and $\text{R}{}_{\mathrm{i}}\text{?R}{}_{\mathrm{j}}$ is the natural join of R_i and R_j.     

Minimizing the Number of States in a Sequential Machine with Don't Care Conditions

Paull and Unger [1] considered the problem of minimizing the number of states in a sequential machine in which some next-states and/or outputs are unspecified and its initial state is unspecified. This note treats the problem where the initial state of the sequential machine is specified. In this case, the condition for covering the machine is weaker and the problem is more complicated. It is shown, however, that one can treat the problem similarly.     

THE COMPUTATIONAL COMPLEXITY OF THE UNIVERSAL RECOGNITION PROBLEM FOR PARALLEL MULTIPLE CONTEXT-FREE GRAMMARS

A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context-free grammars, multiple context-free grammars, and their subclasses are discussed.     

Development of a liquid-xenon photon detector--towards the search for a muon rare decay mode at Paul Scherrer Institute

We are developing a new type of photon detector in preparation of an experiment to search for muons decaying into positrons and gamma rays. In the experiment, the photon detector will utilize liquid xenon (Xe) as the scintillation material because of its fast response, large light yield, and high density. The scintillation light emitted in liquid Xe will be observed directly by positioning photomultipliers (PMTs) in the liquid without using a transmission window. In order to determine proper experimental procedures and to study the detector response to gamma rays, we constructed a prototype utilizing a 100 l volume of liquid Xe. The current status and future prospects of detector development are reported in this article.     

On linear structure and phase rotation invariant properties ofblock M-PSK modulation codes

Two important structural properties of block M(=2^' )-ary PSK modulation codes, linear structure and phase symmetry, are investigated. An M-ary modulation code is first represented as a code with symbols from the integer group S_M-PSK=(0,1,2,---,M-1) under modulo-M addition. Then the linear structure of block M-PSK modulation codes over S_M-PSK with respect to modulo- M vector addition is defined, and conditions are derived under which a block M-PSK modulation code is linear. Once the linear structure is developed, the phase symmetry of block M-PSK modulation codes is studied. In particular, a necessary and sufficient condition for a block M-PSK modulation code that is linear as a binary code to be invariant under 2^h/180°M phase rotation, for 1⩽h⩽l is derived. Finally, a list of short 8-PSK and 16-PSK modulation codes is given, together with their linear structure and the smallest phase rotation for which a code is invariant