In this paper we study a classical firing squad synchronization problem on a model of fault-tolerant cellular automata that have possibly some defective cells. Several fault-tolerant time-efficient synchronization algorithms are developed based on a simple freezing-thawing technique. It is shown that, under some constraints on the distribution of defective cells, any cellular array of length n with p defective cell segments can be synchronized in 2n - 2 + p steps.

Automata based image compression methods exploit similarities in the images to reduce the amount of memory to the essential. Our cellular automata methods are motivated due to the fact that they may be used to create images on liquid crystal displays when we add some computational functionality to the displays. For this purpose we consider image generation methods in cellular automata with some reasonable restrictions and get a representation where the color values of the images can be derived directly from the single cell states. We are interested in the capabilities of such devices and provide some benefits of this representation in image compression, even in higher dimensions.

The descriptional complexity of iterative arrays (IAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that IAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between IAs working in linear time and IAs working in real time. Furthermore, the descriptional complexity of IAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for IAs are undecidable and not semidecidable.

A reversible cellular automaton (RCA) is a computing model having a property analogous to physical reversibility. We investigate the problem of finding simple RCAs in which any circuit composed of rotary elements (REs) can be embedded. Since an RE is known to be a universal reversible logic element, such RCAs are also universal in this respect. In this paper, after giving a survey of known results on RE and its implementation in RCAs, we propose a new RCA model in which REs and some signal routing elements can be embedded. The new model has a simpler local transition function (in the sense it is described by fewer rules) than the previous one, though the number of states is the same. In addition, the patterns realizing an RE and signal routing elements are smaller than those of the previous model.

The floor field model, which is a cellular automaton model for studying evacuation dynamics, is investigated and extended. A method for calculating the static floor field, which describes the shortest distance to an exit door, in an arbitrary geometry of rooms is presented. The wall potential and contraction effect at a wide exit are also proposed in order to obtain realistic behavior near corners and bottlenecks. These extensions are important for evacuation simulations, especially in the case of panics.

In this paper, we investigate how to initialise cellular automata implemented in the hyperbolic plane. We generalise a technique which was indicated in to the case of any rectangular regular grid of the hyperbolic plane. This allows us to construct the initial configuration of any cellular automaton belonging to a rather large class of problems.

This paper investigates relationships among deterministic, nondeterministic, and alternating complexity classes defined in the hyperbolic space. We show that (i) every t(n)-time nondeterministic cellular automaton in the hyperbolic space (hyperbolic CA) can be simulated by an O(t4(n))-space deterministic hyperbolic CA, and (ii) every t(n)-space nondeterministic hyperbolic CA can be simulated by an O(t2(n))-time deterministic hyperbolic CA. We also show that nr+-time (non)deterministic hyperbolic CAs are strictly more powerful than nr-time (non)deterministic hyperbolic CAs for any rational constants r 1 and > 0. From the above simulation results and a known separation result, we obtain the following relationships of hyperbolic complexity classes: Ph= NPh = PSPACEh EXPTIMEh= NEXPTIMEh = EXPSPACEh , where Ch is the hyperbolic counterpart of a Euclidean complexity class C. Furthermore, we show that (i) NPh APh unless PSPACE = NEXPTIME, and (ii) APh EXPTIME h.

The 6to4 method enables separate IPv6 sites to connect to the IPv6 Internet via a 6to4 relay router without an explicit IPv6-over-IPv4 tunnel setup. There are about a dozen open 6to4 relay routers worldwide but none of these have been installed in Japan. We therefore decided to evaluate the 6to4 mechanism and set ourselves the goal of improving the 6to4 operation within Japan. To accomplish this, in March 2002, we installed an open 6to4 relay router in Japan with the cooperation of the WIDE project and started this experiment. This paper describes our experiment and analysis of IPv6 traffic through our 6to4 relay router, as well as considerations derived from our experiment.

This paper studies the propagation and crossing of signals in cellular automata whose cells are updated at random times. The signals considered consist of a core part, surrounded by an insulating sheath that is missing at the side of the core that corresponds to the direction into which the signal moves. We study two types of signals: (1) signals by which the sheath at the left and right sides of the core advance first in a propagation step, followed by the core, and (2) signals by which the core advances first, followed by the sheath at its left and right sides. These types naturally arise in, respectively, Moore neighborhood cellular automata with semi-totalistic rules and von Neumann neighborhood cellular automata with symmetric transition rules. The type of a signal has a profound impact on the way signals cross each other, as we show by the construction of one signal of each type. The results we obtained should be of assistance in constructing asynchronous circuits on asynchronous cellular automata.

Polyurethane elastomer (PUE) films similar to polymer gel materials have been found to exhibit the electrostriction effect. We proposed the application their to a moving device such as an actuator without ionic solvent using the electrostriction effect of PUE. The actuators are of monomorph type fabricated by PUE film and metal electrodes evaporated at different thicknesses on the film surface. Because these actuators work at high voltage more than 1 KV, we controlled the molecular structure of the films by doping C60 derivatives (fullerenol) into PUE so that the actuators could operate under a low voltage. In order to clear the bending mechanism of actuators, we measured the space charge of PUE films using the pulsed electroacoustic method.

The process mapping of the ALD process of HfO2 using HfCl4 and H2O is reported. A thickness uniformity better than 3% was achieved over a 300 mm-wafer at a deposition rate of 0.52 Å/cycle. Usually, H2O purge period is set less than 10 sec to obtain reasonable throughput; however, the amounts of residual impurities (Cl, H) found to be in the order of sub%, and these impurities are piled up near the HfO2/Si interface. In order to reduce the piled up impurities, we proposed a 2-step deposition in which purge period for initial 10-20 cycles was set to be 90 sec and that for remaining cycles was usual value of 7.5 sec. The leakage current is reduced to 1/10 by using this 2-step deposition.

A new spectrum management architecture for a flexible software defined radio (SDR) is proposed. In this architecture, the SDR hardware and software are certified separately so as not to destroy the SDR flexibility, but to ensure that any combinations of hardware and software are compliant to the radio regulations even at the system (vertical) handover, global (horizontal) handover, and upgrade (forward) or downgrade (backward) handover. This architecture is based on automatic calibration & certification unit (ACU), built-in GPS receiver, and radio security module (RSM). The ACU is a hardware embedded RF manager that dynamically controls the output power spectrum to be compliant to the local radio regulation parameters. This local radio regulation parameters are securely downloaded to the hardware as an electronic label of the SDR software and stored in the RSM which is a security manager of the hardware. The GPS position check is used, especially during roaming, to keep the compliancy of the terminal to each local radio regulations managed by the geographical region. The principle parties involved in this architecture are telecommunication certification body (TCB), SDR hardware maker (HW maker), SDR software maker (SW maker), and SDR user. The roles and relationships of these four parties in the proposed architecture are clarified in this paper.

Hyperthermia is one of the modalities for cancer treatment, utilizing the difference of thermal sensitivity between tumor and normal tissue. In this treatment, the tumor or target cancer cell is heated up to the therapeutic temperature between 42 and 45 without overheating the surrounding normal tissues. Particularly, the authors have been studying the coaxial-slot antenna for interstitial microwave hyperthermia. At that time, we analyzed the heating characteristics of the coaxial-slot antenna under the assumption that the human body is a homogeneous medium. In this paper, we analyzed the heating characteristics of the coaxial-slot antenna inside an actual neck tumor by using numerical calculations. The models of calculations consist of MRI tomograms of an actual patient. As a result of the calculations, we observed almost uniform temperature distributions inside the human body including the actual neck tumor, which are similar to the results obtained for a homogeneous medium.

In this paper, we present the results of a comparative analysis of Atomic Broadcast algorithms. The analysis was done by using an analytical method to compare the performance of five different classes of Atomic Broadcast algorithms. The five classes of Atomic Broadcast algorithms are determined by the mechanisms used by the algorithms to define the delivery order. To evaluate the performance of algorithms, the analysis relies on contention-aware metrics to provide a measure for both their latency and their throughput. The results thus obtained yield interesting insight into the performance tradeoffs of different Atomic Broadcast algorithms, thus providing helpful information to algorithms and systems designers.

The recent evolution on the network tomography have successfully provided principles and methodologies of inferring network-internal (local) characteristics solely from end-to-end measurements, which should be followed by deployment in practical use. In this paper, two kinds of user-oriented tools for inferring one-way packet losses based on the network tomography are proposed. They can infer one-way packet loss rates on paths or path segments from/to a user-host (a client) to/from a specified target host (an application server or a router) without any measurement on the target, and thus can find the congested area along the path between the client and an application server. One is a stand-alone tool running on the client, and the other is a client-server style tool running on both the client and a proxy measurement server distributed in the Internet. Prototypes of the tools have been developed and evaluated by experiments in the actual Internet environment, which shows that the tools can infer the loss rates within 1% errors in various network conditions.

Suica is our contact-less IC card's nickname: Super Urban Intelligent CArd. There are two types of IC Card: One for Suica IO (SF) Card and the other for Suica Commuter Pass, which has a function of stored fare card and commuter pass. There are 6.54 million Suica holders (about 3.33 million Suica Season Pass holders and 3.21 million Suica IO Card holders) as of 16, June 2003.

Software and its systems are more complicated than a decade ago, and the systems are used for mission critical business, flight control and so on which often require high assurance systems. In this circumstance, we often use black-box testing. The question now arises that black-box testing does not generate numerical value of testing result but empirical. Thus, in this research, we develop and enhance FSM (Finite State Machine) testing method which can produce code coverage rate as numerical value. Our developed FSM testing by code coverage focuses on not only software system behavior but also data. We found higher code coverage rate, which indicates quality of system, by this method than existing black box testing method.

Automatic image inspector inspects the quality of printed circuit boards using image-processing technology. In this study, we change an automatic inspection problem into a problem for detecting the signal singularities. Based on the wavelet theory that the wavelet transform can focus on localized signal structures with a zooming procedure, a novel singularity detection and measurement algorithm is proposed. Singularity positions are detected with the local wavelet transform modulus maximum (WTMM) line, and the Lipschitz exponent is estimated at each singularity from the decay of the wavelet transform amplitude along the WTMM line. According to the theoretical analysis and computer simulation results, the proposed algorithm is shown to be successful for solving the automatic inspection problem and calculating the Lipschitz exponents of signals. These Lipschitz exponents successfully characterize singular behavior of signals at singularities.

We propose a normalization scheme of syntactic structures using a binary phrase structure grammar with composite labels. The normalization adopts binary rules so that the dependency between two sub-trees can be represented in the label of the tree. The label of a tree is composed of two attributes, each of which is extracted from each sub-tree, so that it can represent the compositional information of the tree. The composite label is generated from part-of-speech tags using an automatic labelling algorithm. Since the proposed normalization scheme is binary and uses only part-of-speech information, it can readily be used to compare the results of different syntactic analyses independently of their syntactic description and can be applied to other languages as well. It can also be used for syntactic analysis, which performs higher than the previous syntactic description for Korean corpus. We implement a tool that transforms a syntactic description into normalized one based on this proposed scheme. It can help construct a unified syntactic corpus and extract syntactic information from various types of syntactic corpus in a uniform way.

This paper introduces a 1-inkdot two-way alternating pushdown automaton which is a two-way alternating pushdown automaton (2apda) with the additional power of marking at most 1 tape-cell on the input (with an inkdot) once. We first investigate a relationship between the accepting powers of sublogarithmically space-bounded 2apda's with and without 1 inkdot, and show, for example, that sublogarithmically space-bounded 2apda's with 1 inkdot are more powerful than those which have no inkdots. We next investigate an alternation hierarchy for sublogarithmically space-bounded 1-inkdot 2apda's, and show that the alternation hierarchy on the first level for 1-inkdot 2apda's holds, and we also show that 1-inkdot two-way nondeterministic pushdown automata using sublogarithmic space are incomparable with 1-inkdot two-way alternating pushdown automata with only universal states using the same space.