In this paper, the computational issue in the problem of learning Bayesian belief networks (BBNs) based on the minimum description length (MDL) principle is addressed. Based on an asymptotic formula of description length, we apply the branch and bound technique to finding true network structures. The resulting algorithm searches considerably saves the computation yet successfully searches the network structure with the minimum value of the formula. Thus far, there has been no search algorithm that finds the optimal solution for examples of practical size and a set of network structures in the sense of the maximum posterior probability, and heuristic searches such as K2 and K3 trap in local optima due to the greedy nature even when the sample size is large. The proposed algorithm, since it minimizes the description length, eventually selects the true network structure as the sample size goes to infinity.

Predicate Circumscription is a fundamental formalization of common sense reasoning. In this paper, we study a new approximation formula of it. In our previous works, we investigated Lifschitz's pointwise circumscription and its generalization, which functions as a finite approximation to predicate circumscription in the first-order framework. In this paper, at first, we study the ability of the generalized pointwise circumscription more closely, and give a simple example which shows that it cannot be complete even when a minimized predicate has only finite extension on the minimal models. Next, we introduce a new approximation formula, called finite constructive circumscription, in order to overcome that limitation. Finally, we compare expressive power of the two approximation methods with of predicate circumscription schema, and propose a open problem that should be solved to clarify that the completeness of predicate circumscription schema with respect to minimal model semantics.

This study presents a method that can be used to manage individual pieces of information in large scale distributed geographic information systems (GIS). In a distributed GIS, ordinary users usually cannot alter any of the contents on the server. The method in this study can be used to alter the content or add individual datums onto these types of non-write-permitted data sets. The authors have called it a 'Geographic Differential Script File' (GDSF). A client creates a GDSF, which contains private information that is to be added onto the served data. The client keeps this file on a local disk. When the user employs the data, he applies the differential script sequence onto the downloaded data in order to retrieve the information. GDSF is a collection of graphic operation commands which insert and delete objects as well as modify operations. GDSF also contains modifications of the attribute information of geographic entities. This method can also be used to revise information that is published on ROM media, e. g. CD-ROM or DVD-ROM, as well as in a distributed environment. In this paper, the method and results of applying it are presented.

Providing various assistances for design modifications on HDL source codes is important for design reuse and quick design cycle in VLSI CAD. Program slicing is a software-engineering technique for analyzing, abstracting, and transforming programs. We show algorithms for extracting/removing behaviors of specified signals in VHDL descriptions. We also describe a VHDL slicing system and show experimental results of efficiently extracting components from VHDL descriptions.

When wireless multi-media information such as voice, video, data and so on are transmitted, the difference required quality of Service (QoS) including required Bit Error Rate (BER), required information bit rate, message's delay constraints as well as traffic performance should be taken into account. A wireless multi-media system should achieve a flexible balance of these differences. In this letter, an Adaptive Chip/Bit Control Method is proposed for Wireless Multi-media CDMA System. The proposed method controls both chip and bit rate of each medium according to the offered traffic condition and the quality measurement of each medium. In the proposed method, measurement are carried out in the base station. Simulation results show that the proposed method not only maintain the required BER of each medium, but achieve a higher total throughput even in high traffic condition. Thus we see that the proposed method possesses higher flexible ability than conventional methods.

Space Division Multiple Access (SDMA) will form an important part of the new Wideband Code Division Multiple Access (WCDMA) standard that will realize the Universal Mobile Telephone System (UMTS). This paper addresses a few issues of importance when SDMA techniques are used in a cellular CDMA system. Firstly, a brief overview of SDMA techniques are presented followed by a theoretical analysis of a SDMA/CDMA system. The analysis is focused on a single cell, multipath Rayleigh fading scenario with imperfect power control. As system performance measure Bit Error Rate (BER) is used to investigate the influence of user location, number of antennas and power control error. An important parameter in a SDMA system is the antenna array element spacing. In our analysis a Uniform Linear Array (ULA) is considered and a measure is defined to determine the optimal antenna element spacing in a CDMA cellular environment. Normally the mobile users in a cell are assumed to be uniformly distributed in cellular performance calculations. To reflect a more realistic situation, we propose a novel probability density function for the non-uniform distribution of the mobile users in the cell. It is shown that multipath and imperfect power control, even with antenna arrays, reduces the system performance substantially.

In the commonsense reasoning, priorities among rules are often required to be found out in order to derive the desired conclusion as a theorem of the reasoning. In this paper, first we present the bottom-up and top-down abduction procedures to compute skeptical explanations and secondly show that priorities of circumscription to infer a desired theorem can be abduced as a skeptical explanation in abduction. In our approach, the required priorities can be computed based on the procedure to compute skeptical explanations provided in this paper as well as Wakaki and Satoh's method of compiling circumscription into extended logic programs. The method, for example, enables us to automatically find the adequate priority w. r. t. the Yale Shooting Problem to express a human natural reasoning in the framework of circumscription.

We propose an architectural reference of programmable devices that we call Plastic Cell Architecture (PCA). PCA is a reference for implementing a device with autonomous reconfigurability, which we also introduce in this paper. This reconfigurability is a further step toward new reconfigurable computing, which introduces variable- and programmable-grained parallelism to wired logic computing. This computing follows the Object-Oriented paradigm: it regards configured circuits as objects. These objects will be described in a new hardware description language dealing with the semantics of dynamic module instantiation. PCA is the fusion of SRAM-based FPGAs and cellular automata (CA), where the CA are dedicated to support run time activities of objects. This paper mainly focus on autonomous reconfigurability and PCA. The following discussions examine a research direction towards general-purpose reconfigurable computing.

A simple digital circuit based on the probabilistic cellular automata is proposed whose temporal evolution generates 1/f noise over many frequency decades. The N cells with internal states form a one-dimensional network and probabilistically interact with nearest-neighbor ones. The internal state of the cell is either the stable state or the unstable state. Each cell obeys simple rules as follows. When the excitatory signal is applied to the cell in the stable state, the state changes to the unstable state. On the other hand, when the state is unstable, the state changes to the stable state, and then the cell generates the excitatory signal. The excitatory signal is applied to the cell which is randomly chosen between the right side cell and the left side cell. The edge condition of the network is open, so that the excitatory signal can leave both the first edge and the last edge. The excitatory signal is randomly added to the first edge of the network at intervals of T time. Then the sequential interactions may occur like avalanche breakdown. After the interactions, the network goes to the equilibrium state. Considering that the breakdown happen simultaneously and assigning the stable state and the unstable state to 0 and 1, respectively, one can get the random pulse stream on the internal state of each cell. The power spectra of pulse streams are Lorentzian with various pole frequencies. The probability distribution of the pole frequency is inversely proportional to the frequency, i. e. , obeys Zipf law. Then the total sum of the internal states of all cells fluctuates following 1/f power law. The frequency range following 1/f power law can be easily varied by changing the number of the cells for the summation. A prototype generator using 15 cells generates 1/f noise over 3 frequency decades. This simple circuit is composed of only full adders and needs not complex components such as multipliers. Fine-tuning of any parameters and precise components also are not needed. Therefore integration into one chip using standard CMOS process is easy.

A multimedia coding standard, MPEG4 has frozen its Committee Draft (CD) as the MPEG4 version 1 CD, last October. It defines Audio-Visual (AV) coding Algorithms and their System Multiplex/Composition formats. Founding on Object-base concept, Video part adopts Shape Coding technology in addition to conventional Texture Coding skills. Audio part consists of voice coding tools (HVXC and CELP core) and audio coding tools (HILN and MPEG2 AAC or Twin VQ). Error resilience technologies and Synthetic and Natural Hybrid Coding (SNHC) technologies are the MPEG4 specific features. System part defines flexible Multiplexing of audio-visual bitstreams and Scene Composition for user-interactive re-construction of the scenes at decoder side. The version 1 standardization will be finalized in 1998, with some possible minute changes. The expected application areas are real-time communication, mobile multimedia, internet/intranet accessing, broadcasting, storage media, surveillance, and so on.

In this paper, we propose a descriptor as a shape signature and the projective refinement as a verification method for recognizing 2D curved objects with occlusions from their partial views. For an extracted curve segment, we compute a series of the geometric invariance of equally spaced five co-planar points on the curve. Thus the resulting descriptor is invariant only under rotation, translation, and scale, but sufficient similarity is preserved even under large distortions. It is more stable and robust since it does not need derivatives. We use this transformation-invariant descriptor to index a hash table. We show the efficiency of the method through experiments using seriously distorted images of 2-D curved objects with occlusions.

The asymptotic behavior of the recurrence time with fidelity criterion is discussed. Let X= be a source and Y= a database. For a Δ>0 and an integer l>0 define (Y,X,Δ) as the minimum integer N satisfying dl(,) Δ subject to a fidelity criterion dl. In this paper the following two i. i. d. cases are considered: (A) Xi P and Yi Q, where P and Q are probability distributions on a finite alphabet, and (B) Xi N(0,1) and Yi N(0,1). In case (A) it is proved that (1/l)log2(Y,X,Δ) almost surely converges to a certain constant determined by P, Q and Δ as l. The Kac's lemma plays an important role in the proof on the convergence. In case (B) it is shown that there is a quantity related to (1/l)log2 (Y,X,Δ) that converges to the rate-distortion bound in almost sure sense.

This study presents a novel window-based token protocol which supports two priority levels of ATM-like bursty traffic. The proposed protocol ensures that packets arriving during a given window period are always transmitted prior to those arriving during subsequent window periods. During which periods, high priority (delay-sensitive) packets are served by a nonpreemptive priority service discipline. Under this window-based token protocol, the delay bounds for packets of both priority levels are derived when the traffic streams satisfy the traffic descriptors. Hence, a call admission control policy based on delay bounds can be employed to guarantee QoS parameters such as the packet delay and packet loss-free requirement for each traffic stream. The protocol proposed herein can achieve tighter delay bounds than the IEEE 802. 5 token protocol and the timed token protocol used in FDDI, particularly for high priority bursty traffic, thereby making it highly attractive for supporting not only real-time multimedia VBR or CBR services such as in ATM networks but also ATM encapsulation such as in Cells In Frames (CIF) protocol.

Considering the pattern classification/recognition tasks, the influence of the activation function on fault tolerance property of feedforward neural networks is empirically investigated. The simulation results show that the activation function largely influences the fault tolerance and the generalization property of neural networks. It is found that, neural networks with symmetric sigmoid activation function are largely fault tolerant than the networks with asymmetric sigmoid function. However the close relation between the fault tolerance and the generalization property was not observed and the networks with asymmetric activation function slightly generalize better than the networks with the symmetric activation function. First, the influence of the activation function on fault tolerance property of neural networks is investigated on the XOR problem, then the results are generalized by evaluating the fault tolerance property of different NNs implementing different benchmark problems.

This paper proposes practical escrow cash schemes with particular emphasis on countermeasures against social crimes such as money laundering and extortion. The proposed cash schemes restrict "unconditional" privacy in order to prevent these social crimes while preserving off-line-ness, divisibility and transferability, properties listed in [25] as criteria for ideal cash schemes.

We propose a new method for verifying synchronous circuits using the Boyer-Moore Theorem Prover (BMTP) based on an efficient use of induction. The method contains two techniques. The one is the representation method of signals. Each signal is represented not as a waveform, but as a time parameterized function. The other is the mechanical transformation of the circuit description. A simple description of the logical connection of the components of a circuit is transformed into such a form that is not only acceptable as a definition of BMTP but also adequate for applying induction. We formalize the method and show that it realizes an efficient proof.

S-boxes (vector output Boolean functions) should satisfy cryptographic criteria even if some input bits (say, k bits) are kept constant. However, this kind of security has been studied only for scalar output Boolean functions. SAC (k) is a criterion for scalar output Boolean functions of this type. This paper studies a generalization of SAC (k) to vector output Boolean functions as the first step toward the security of block ciphers against attacks which keep some input bits constant. We first show a close relationship between such Boolean functions and linear error correcting codes. Then we show the existence, bounds and enumeration of vector Boolean functions which satisfy the generalized SAC (k). A design method and examples are also presented.

This paper proposes high-speed similitude retrieval schemes for a viewpoint-based similarity discrimination system (VB-SDS) and presents analytical and experimental performance evaluations. The VB-SDS, which contains a huge set of semantic definitions of commonly used words and computes semantic similarity between any two words under a certain viewpoint, promises to be a very important module in analogical and case-based reasoning systems that provide solutions under uncertainty. By computing and comparing similarities for all words contained in the system, the most similar word for a given word can be retrieved under a given viewpoint. However, the time this consumes makes the VB-SDS unsuitable for inference systems. The proposed schemes reduce search space based on the upper bound of a similarity calculation function to increase retrieval speed. An analytical evaluation shows the schemes can achieve a thousand-fold speedup and confirmed through experimental results for a VB-SDS containing about 40,000 words.

In general cases of pattern recognition, a pattern to be recognized is first represented by a set of features and the measured values of the features are then classified. Finding features relevant to recognition is thus an important issue in recognizer design. As a fundamental design framework taht systematically enables one to realize such useful features, the Subspace Method (SM) has been extensively used in various recognition tasks. However, this promising methodological framework is still inadequate. The discriminative power of early versions was not very high. The training behavior of a recent discriminative version called the Learning Subspace Method has not been fully clarified due to its empirical definition, though its discriminative power has been improved. To alleviate this insufficiency, we propose in this paper a new discriminative SM algorithm based on the Minimum Classification Error/Generalized Probabilistic Descent method and show that the proposed algorithm achieves an optimal accurate recognition result, i.e., the (at least locally) minimum recognition error situation, in the probabilistic descent sense.

This paper presents an event-driven approach to the timing verification of latch-synchronized systems. The proposed method performs critical path extraction and timing error detection at the same time, and extracts the critical path only if necessary. By doing so, the complexity of analysis is reduced and efficiency is greatly improved over the conventional approaches which detect timing errors after extracting the complete critical paths of the system. Experimental results show that, compared to the existing methods, it provides a more than 12-fold improvement in speed on the average for ISCAS benchmark circuits, and the relative efficiency of analysis improves as the circuit size grows.