In this paper, a recognition algorithm for the class of tree languages generated by linear, monadic context-free tree grammars (LM-CFTGs) is proposed. LM-CFTGs define an important class of tree languages because LM-CFTGs are weakly equivalent to tree adjoining grammars (TAGs). The algorithm uses the CKY algorithm as a subprogram and recognizes whether an input tree can be derived from a given LM-CFTG in O(n4) time, where n is the number of nodes of the input tree.

A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages so that edges are allowed to cross the spine. Recently, the author has shown that for an arbitrary graph G with n vertices there exists a d+1-page book embedding of G in which each edge crosses the spine logd n times. This paper improves the result for the case of bipartite graphs and shows that there exists a d+1-page book embedding of a bipartite graph Gn1,n2 having two partite sets with n1 and n2 vertices respectively (n1 ≥ n2) in which each edge crosses the spine logd n2 -1 times.

There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.

A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages; edges are allowed to cross the spine. Enomoto showed that for any graph G having n vertices, there exists a three-page book embedding of G in which each edge crosses the spine log n times. This paper generalizes the result and shows that for any graph G having n vertices, there exists a d + 1-page book embedding of G in which each edge crosses the spine logd n times.

Quantum dots are one of the possible building blocks for the quantum computing device. We discuss on use of carbon nanotubes for fabrication of the quantum dot, in terms of their unique physical properties and energy scales which might be advantageous for functionalities of the quantum computing device. Simple schemes of a charge qubit and a spin qubit are described, followed by the current status of the fabrication and transport measurements of the nanotube quantum dot. Based on the basic properties and the estimated energy scales of the dot, we discuss advantages and problems of the carbon nanotube for the quantum computing device. The nanotube quantum dot may have a great advantage for the spin qubit.

This paper proposes the design of a physically accurate spine model and its application to estimate three dimensional spine posture from the frontal and lateral views of a human body taken by two conventional video cameras. The accurate spine model proposed here is composed of rigid body parts approximating vertebral bodies and elastic body parts representing intervertebral disks. In the estimation process, we obtain neck and waist positions by fitting the Connected Vertebra Spheres Model to frontal and lateral silhouette images. Then the virtual forces acting on the top and the bottom vertebrae of the accurate spine model are computed based on the obtained neck and waist positions. The accurate model is deformed by the virtual forces, the gravitational force, and the forces of repulsion. The model thus deformed is regarded as the current posture. According to the preliminary experiments based on one real MR image data set of only one subject person, we confirmed that our proposed deformation method estimates the positions of the vertebrae within positional shifts of 3.2 6.8 mm. 3D posture of the spine could be estimated reasonably by applying the estimation method to actual human images taken by video cameras.

Magnetic random access memory (MRAM) possesses the attractive properties of non-volatility, radiation hardness, nondestructive readout, low voltage, high access speed, unlimited read and write endurance and high density. MRAM technology is described for the devices using giant magnetoresistance (GMR) and tunneling magnetoresistance (TMR) materials in this paper. The TMR type MRAM architectures using ferromagnetic tunneling junctions (MTJ) are more attractive for mainstream RAM applications than the GMR type, because the signal of the TMR type is larger than that of the GMR type. A MRAM device with an MTJ plus MOS transistor switch architecture, which can provide large signal-to noise ratio, is detailed. A design of the MTJ element is discussed and the requirements for the junction resistance and the TMR needed for the memory device are demonstrated based on the simple signal voltage calculations. The TMR significantly decreases with increasing bias voltage, which leads to the reduction of the signal voltage for the actual MRAM. A ferromagnetic double tunneling junction is proposed for the high density MRAM application demanding large signal voltage, because of the smaller degradation of the TMR for the bias voltage, compared with that of the conventional single junctions. Recent trials of MRAM fabrication are introduced, which demonstrates high-speed access time. Finally, challenges for the higher bit density MRAM above Gb are discussed, and it is noticed that higher signal voltage, lower power consumption for writing and novel cell designs are needed for the achievement.

This paper studies the problem of book-embeddings of graphs. When each edge is allowed to appear in one or more pages by crossing the spine of a book, it is well known that every graph G can be embedded in a 3-page book. Recently, it has been shown that there exists a 3-page book embedding of G in which each edge crosses the spine O(log2 n) times. This paper considers a book with more than three pages. In this case, it is known that a complete graph Kn with n vertices can be embedded in a n/2 -page book without any edge-crossings on the spine. Thus it becomes an interesting problem to devise book-embeddings of G so as to reduce both the number of pages used and the number of edge-crossings over the spine. This paper shows that there exists a d-page book embedding of G in which each edge crosses the spine O(logd n) times. As a direct corollary, for any real number s, there is an ns -page book embedding of G in which each edge crosses the spine a constant number of times. In another paper, Enomoto-Miyauchi-Ota show that for an integer d, if n is sufficiently large compared with d, then for any embedding of Kn into a d-page book, there must exist Ω(n2 logd n) points at which edges cross over the spine. This means our result is the best possible for Kn in this case.

This paper reports on the development of an eyeglass-type infrared-controlled telephone communication interface for the disabled. This system is comprised of four major components: A) a headset; B) an infrared transmitting module; C) an infrared receiving/signal-processing module; and D) a main controller, the Intel-8951 microprocessor. The headset with a tongue-touch panel, a wireless earphone, and a wireless microphone. The infrared transmitting module utilizes a tongue touch panel via tongue-touch circuitry which is converted to an infrared beam and a low power laser (<0.1 mW) beam. The infrared receiving/signal-processing module, receives the infrared beam and fine tunes the unstable infrared beam into standard pulses which are used as control signals. The main controller is responsible for detecting the input signals from the infrared receiving/signal-processing module and verifying these signals with the mapping table in its memory. After the signal is verified, it is released to control the keys of the telephone interface. This design concept was mainly based on the idea that the use of an infrared remote module fastened to the eyeglasses could allow the convenient control of the dialing motion on the keys of a telephone's dialing-pad which are all modified with infrared receiving/signal-processing modules. The disabled are competent for some of work, such as a telephone operator. The increase of opportunity to do a job for the disabled would help them live independently.

A novel analog-computation system using quantum-dot spin glass is proposed. Analog computation is a processing method that solves a mathematical problem by applying an analogy of a physical system to the problem. A 2D array of quantum dots is constructed by mixing two-dot (antiferromagnetic interaction) and three-dot (ferromagnetic interaction) systems. The simulation results show that the array shows spin-glass-like behavior. We then mapped two combinatorial optimization problems onto the quantum-dot spin glasses, and found their optimal solutions. The results demonstrate that quantum-dot spin glass can perform analog computation and solve a complex mathematical problem.

This paper addresses the important issue of estimating realistic grasping postures, and presents a methodology and algorithm to automate the generation of hand and body postures during the grasp of arbitrary shaped objects. Predefined body postures stored in a database are generalized to adapt to a specific grasp using inverse kinematics. The reachable space is represented discretely dividing into small subvolumes, which enables to construct the database. The paper also addresses some common problems of articulated figure animation. A new approach for body positioning with kinematic constraints on both hands is described. An efficient and accurate manipulation of joint constraints is presented. Obtained results are quite satisfactory, and some of them are shown in the paper. The proposed algorithms can find application in the motion of virtual actors, all kinds of animation systems including human motion, robotics and some other fields such as medicine, for instance, to move the artificial limbs of handicapped people in a natural way.

In order to improve the sensitivity of micromachined sensors applied with electrostatic fields and increase their actuated force of electrostatic micromachined actuators, "electrets," which are dielectrics carrying non equilibrium permanent space charges of polarization distribution, are very important. In this paper, positively corona charged silicon dioxide electrets, which are deposited by Plasma Chemical Vapor Deposition (PCVD) and thermally oxidized, are investigated. Physical studies will be described, in which the charge stability is correlated to Thermally Stimulated Current (TSC) measurements and to Electron Spin Resonance (ESR) analysis. Some intrinsic differences have been observed between materials. The electrets with superior long-term charge stability contain 10,000 times as much E' center (Si3 as the ones with inferior long-term charge stability. Finally, some investigations on the long-term charge storage mechanism of the positively charged silicon dioxide electret will be described.

Ba ferrite films were deposited epitaxially on ZnO underlayer from targets with composition of BaO-6.5Fe2O3 at substrate temperature of 600 using the facing targets sputtering apparatus. The gas mixture of Ar and Xe of 0.18 Pa and O2 of 0.02 Pa was used as the sputtering gas and the dependences of crystallographic and magnetic characteristics on the partial Xe pressure PXe(0.0-0.18 Pa) were investigated. Films deposited at various PXe were composed of BaM ferrite and spinel crystallites, and the minimum centerline average roughness Ra of 8.3 nm was obtained at PXe of 0.10 Pa. Since saturation 4πMs of 5.1 kG and perpendicular anisotropy constant Ku1 of 4.23105 Jm-3 were larger than those of bulk BaM ferrite of 4.8 kG and 3.30105 Jm-3, respectively, these films appeared promising for use as perpendicular recording media.

This paper proposes a new strategy for reducing contention for a critical section in a multiprocessor system and shows that the strategy can improve CPU utilization by several percent. Using simulation and queueing theory, it also discusses when the strategy is superior to conventional ones.