bluuebunny/crossref_metadata_2025_split huggingface dataset:
An experimental evaluation of leader election algorithms for ring networks
Authors: Ikegawa Yukinori , Yamashita Masafumi , Ae Tadashi 
Published: July 2007

AbstractThe leader election problem is a problem of determining a unique leader, in the sense that the elected leader knows that it is elected and the processors which are not elected know that they are not elected. Under the assumption that the processors have unique identifiers, the problem can be regarded as the maximum (identifier) finding problem.This paper considers ten typical leader election algorithms for the ring network and evaluates them in terms of the average number of messages exchanged during computation.
Learning and production of speech pattern using multilayer neural networks
Authors: Komura Mitsuo , Tanaka Akio 
Published: July 2007

AbstractA new neural network and its learning algorithm are proposed. The neural network consists of four layers—input, hidden, output and final output layers. The hidden and output layers are multiple. The proposed learning algorithm is called the SICL (spread pattern information and cooperative learning) method and has the following features: (1) the singular points of back propagation errors in the BP method are removed; (2) a spread pattern information (SI) algorithm is proposed; and (3) a cooperative learning (CL) algorithm is proposed.Using the SICL method, it is possible to learn analog data accurately and to obtain a stable output. Using this neural network, the authors developed a speech production system consisting of a phonemic symbol production subsystem and a speech parameter production subsystem. The system is applied to speech data and the system performance is examined. Especially, for the speech parameter production subsystem, the learning capacity and the optimal area for learning constants are studied. As a result, it is shown that it is possible to learn and produce speech data with high accuracy using the proposed neural network.
Bidirectional inference of mode information for logic programs
Authors: Zhou Neng‐Fa , Ushijima Kazuo , Takagi Toshihisa 
Published: July 2007

AbstractMode information (directional information concerning the arguments of predicates) is important in improving the speed of the execution of logic programs. This paper proposes a bidirectional inference algorithm for inferring precise mode information. Compared with the conventional inference algorithms, the proposed algorithm has the following two features: (1) the algorithm utilizes not only the modes of the predicates at the top level but also the modes of the built‐in predicates used in the program; and (2) by propagating the modes of the top level predicates top‐down and that of the built‐in predicates bottom‐up, more precise mode information can be inferred.
A highly reliable large scale computer complex
Authors: Turuho Seishiro , Nakatani Hajime , Gohara Juniti 
Published: July 2007

AbstractTo realize a highly reliable large‐scale distributed function system composed of a number of HOST and FEP, it is necessary that the fault detection of the HOST and FEP processors, as well as the switching to the back‐up processor, be conducted at a high speed.This paper considers a hot standby system with N operating processors and 1 standby processor. A method of high‐speed recovery from the processor fault and the centralized monitoring by the system control processor (SCP) are described. In the proposed method, SCP detects the generation of fault in HOST or FEP, and instructs the switching to the standby processor. In the recovery from a fault in HOST, the communication path to the terminal is maintained by FEP, and the received message is kept in FEP until the switching of HOST is completed.It is shown also that the recovery in approximately half the time needed in the conventional system realized in FEP fault, and the availability of FEP is improved by one order of magnitude, by floating the standby.By these elaborations, the switching time to the standby in the fault of HOST and FEP is reduced drastically in a large‐scale function distributed system with several thousands of terminals. It is verified that in the fault of HOST, the response message can be returned to most of the terminals within the response monitoring time, and the system fault can be concealed from most terminal users.
Subclasses of Linear Context—Free Languages and Homomorphic Characterizations of Languages
Authors: Okawa Satoshi , Hirose Sadaki 
Published: July 2007

AbstractThis paper defines the right‐longer (left‐longer) linear grammars with the property for every production rule as natural variants of even linear grammars definedThe relation is investigated among the language classes generated by those grammars, regular grammars, and linear context‐free grammars. Also investigated are the closure properties under some basic set operations.Finally, new homomorphic characterizations are given as follows. For every recursively enumerable language L, we can find two languages L1, L2 from each pair of those language classes except a pair of even linear languages and a homomorphism h such that L=h(L1L2). For the remainder pair, a result that h(L1L2) is linear context‐free is obtained.
Detection of Broken Ellipses by the Hough Transforms and Multiresolutional Images
Authors: Watanabe Takashi , Shibata Toshihiro 
Published: July 2007

AbstractThis paper discusses the problem of separating and detecting ellipse patterns. The traditional ellipse detection methods have assumed contour lines to be connected. Thus, they have the disadvantage of not being able to detect ellipses whose contours are broken considerably due to noise and overlapping. Thus, a new ellipse detection algorithm is presented which can cope with images such that many ellipses of arbitrary shapes are mixed and connectivities of contours are missing completely due to noise, and that parts of contours are lost because of overlapping.The proposed algorithm is based on the Merlin‐Farber method, a kind of Hough transforms, and the multiresolutional images and the least‐square method are incorporated. Good detection results were obtained in the experiments implemented to demonstrate the effectiveness of the proposed method.
Extracting depth‐information from dynamic image by spatio‐temporal correlation analysis
Authors: Nomura Atsushi , Miike Hidetoshi , Koga Kazutoshi 
Published: July 2007

AbstractOptical flow‐field obtained by the analysis of a sequential scene derived by a relative motion between object and camera includes three‐dimensional information (depth and/or shape).This paper develops a spatio‐temporal correlation method for determining optical flow and attempts to extract the depth information on the basis of the analyzed optical flow field and the principle of the “motion stereo.” The method herein is improved in two critical points: (1) analysis of the plane wave propagation; and (2) algorithms for rapid calculation. It is demonstrated that the improved method and the theory of “motion stereo” are available for extracting depth information from actual scenes.
Multiprocessor scheduling algorithm with communication time
Authors: Kitagawa Hideo , Matsuda Fumio , Uchikawa Yoshiki , Hattori Shuzo 
Published: July 2007

AbstractThis paper proposes an algorithm for multiprocessor scheduling which is needed to realize efficient parallel processing. In the traditional multiprocessor scheduling algorithms the time required for data communication was neglected to decrease the complexity of combinatorial computation.In this paper, using a scheduling algorithm which incorporates elements of communication time into a suboptimal algorithm, divided tasks are assigned onto a multiprocessor system. The characteristics of this algorithm are two‐fold: first, since the time required for data communication between processors as a parameter is taken into consideration, scheduling conforming to practical systems is possible; second, since it is based on a suboptimal algorithm, it shortens the time required for scheduling. Furthermore, as examples of applications of this algorithm, it is described how it is applied to inverse kinematics and inverse dynamics problems.
A fault‐tolerant algorithm for election in complete networks with a sense of direction
Authors: Masuzawa Toshimitsu , Nishikawa Naoki , Hagihara Ken'Ichi , Tokura Nobuki 
Published: July 2007

AbstractConsider a directed Hamilton cycle H on a complete network. If each processor can distinguish its incident links by the distance on H, the Hamilton cycle is said to have the sense of direction. It is known that the communication complexity of the leader election problem can be reduced by using the sense of direction when there exists no failure in the network.This paper considers the complete network with the sense of direction where at most fp processors (fp < n/2, where n is the total number of processors in the network) are in the fail‐stop condition and presents an algorithm which solves the leader election problem with the communication complexity O(n + k.fp) (k is the number of initiating processors). The result implies that the sense of direction can be used to reduce the communication complexity of the leader election problem also in the complete network with fail‐stop processors. It is shown also that the communication complexity of the presented algorithm is optimal within a constant factor.
The complexity measure of program based on the inter‐module dependency
Authors: Yang Haesool , Tsujino Yoshihiro , Tokura Nobuki 
Published: July 2007

AbstractThe complexity of the program is one of the useful measures in the objective and quantitative evaluation of the software. However, in the past measures, the complexity is evaluated based only on a single factor, such as program size, flow of control or dataflow information. This paper aims at solution of the problems in the past measures and proposes a new measure for the complexity of the program, called MCM (module complexity metrics), which is obtained as a combination of the intermodule dependencies.The feature of the proposed measure MCM is that various factors affecting the complexity of the module can be evaluated in an integrated way. Then the correlation between the proposed measure MCM and the conventional typical measures are analyzed, and it is shown that the complexity of the program can be evaluated more accurately by the proposed measure MCM, while maintaining the properties owned by the past measures.
A modification support system‐automatic correction of side effects caused by type modifications
Authors: Tenma Takao , Sato Yasuomi , Morimoto Yasuhiko , Tanaka Minoru , Ichikawa Tadao 
Published: July 2007

AbstractA programmer modifies software for various reasons, e.g., a change of its requirements or bug correction. When a modification is made in the software, the effect of the modification propagates to various points of the software. Such side effects must be corrected. By automating the correction procedure for the effects produced by the modification, the productivity and the reliability of the software development will be improved. This paper discusses the software modification support and proposes an automatic method of correction for the type modification in the program. The modification support system developed based on the proposed idea is described.
Extraction of transformations to be tested from the structured external functional specification
Authors: Kaneko Takeshi , Nakajo Takeshi 
Published: July 2007

AbstractThe authors propose a software testing method for the detection of modification errors caused by functional specification changes. In the method, if inappropriate transformations are selected, the following problems may occur: (1) test cases cannot be obtained, (2) efficiency becomes worse, and (3) effectiveness declines.This paper identifies the transformations that the method can most effectively apply, employing Hatley's model as a software functional specification description model. It introduces the concept “change level” based on the analysis of actual software defects and shows that: (1) the transformations used in the change level are optimal for testing, and (2) when there exist two transformations in the change level whose restrictions are complementary, only one must be tested. The effectiveness of the proposed method is demonstrated by applying the method to an actual software product. The proposed testing method detected 90 percent of the defects due to functional specification changes in a software product. It can readily produce test cases even without automated testing tools when the restrictions consist of simple inequalities or equalities of the input parameters.
Global states monitoring algorithm for distributed system
Authors: Moriyasu Kenji , Soneoka Terunao , Manabe Yoshifumi 
Published: July 2007

AbstractIn distributed systems, there are not only synchronization errors which stop the system but also errors in which each process behaves according to its process definition, yet the system as a whole behaves differently from the requirements. Since many synchronization errors cannot be detected by locally monitoring the state of each process, monitoring system global states is required. Stable global states are the global states with all channels empty, and monitoring them is known to be important for detecting loss of synchronization in distributed systems, i.e., the presence of unintended global states or the absence of intended ones.This paper describes a method of monitoring stable global states during the operation of distributed systems. This paper first clarifies the lower bound of control information, which each process should record for detection of stable global states, under the assumption that all control information is piggybacked with ordinary system messages. A stable global state monitoring algorithm is then presented, whose control information is minimum and which has minimum‐order complexity.
A linear algorithm for motion of rigid objects using features of parallel lines and optical flow
Authors: Joko Takuto , Ito Koji , Tsuji Toshio , Terauchi Mutsuhiro 
Published: July 2007

AbstractVarious approaches have been proposed toward the problem of restoring three‐dimensional (3‐D) structures and motion of rigid bodies from image information. Ullman and Huang presented algorithms using point and line correspondences, in which they assume that the correspondence problems can be solved. Prazdny et al., on the other hand, presented an algorithm using optical flow, in which equations become nonlinear and thus the second derivative of velocity is required.This paper proposes an algorithm which combines optical flow and edge information. First, considering segments consisting of edges in an image, we derive an equation for optical flow. Then, making use of parallelism of line segments, we show that 3‐D motion can be restored by using linear equations. To apply the algorithm there must exist two pairs of parallel line segments on an object. This paper presents an algorithm for extracting these pairs of parallel line segments. Finally, we verify the effectiveness of the algorithm by simulation.
Back‐propagation learning of neural networks for translation invariant pattern recognition
Authors: Yi Jianqiang , Kurogi Shuichi , Matsuoka Kiyotoshi 
Published: July 2007

AbstractIn many pattern recognition tasks (e.g., handwritten letters), it is essential to recognize a given pattern invariantly with translation, rotation, and other spatial transformations to which the pattern might be subjected. The Fourier transform method is a well‐known method for translation invariant pattern recognition in which the Fourier spectrum of an image is used as an invariant feature.This paper shows experimentally that a three‐layer neural network learns to have a similar capability to that of the Fourier transform method by means of the back propagation learning, during which a set of random dot patterns are repeatedly presented with various positions. Specifically, each unit in the middle layer of the resultant network detects a particular frequency component contained in the given image; and, using the information, the output layer generates an output pattern which is invariant to translation of the image.
Phoneme recognition with elliptic discrimination neural units
Authors: Kanedera Noboru , Funada Tetsuo 
Published: July 2007

AbstractMany researchers achieved high phoneme recognition rates by multilayered neural networks with linear discrimination neural (LDN) units. However, it is difficult to analyze which components of the input are important to each unit in those LDN networks.This paper proposed a multilayer neural network with elliptic discrimination neural (EDN) units so that the functions of each unit in the network may be interpreted more definitely. The center of the elliptic discrimination boundary of a neural unit corresponds to a typical point in an input space. The radii of the ellipse express the extent of the corresponding components in the input space, hence it becomes clear which components of the input space are important to each unit in the EDN network.To compare the performance of EDN and LDN networks, recognition experiments of phonemes /b, d, g/ in 5240 tokens of a Japanese speech database were carried out. In the experiments, recognition rates were obtained by EDN networks as high as the rate by an LDN network. Also, it was confirmed which components of the input space are important to each unit in the EDN network.
Graph representation of logic functions to design two‐level MOS networks
Authors: Nishitani Yasuaki , Shimizu Kensuke , Nagumo Masahiko 
Published: July 2007

AbstractThe design problem of two‐level MOS networks with a minimum number of cells is reduced to the covering problem of graphs with a minimum number of cliques.When every node of the graph corresponds to a minterm, an algorithm which generates an MOS network with a minimum number of cells is presented. The time complexity of this algorithm is O(M)2, where M is the number of minterms.When every node of the graph corresponds to a prime implicant, a procedure which generates near optimum solutions by selecting prime implicants with special properties is presented. About 2 percent of designed networks for four‐variable functions are not minimal ones.
A searching method of the most similar string in the file of a document retrieval system
Authors: Kobayashi Kiyohiro , Imamura Tsuguyasu , Takahashi Masashi , Kubota Fumiko , Kanaoka Taiho , Hamamoto Yoshihiko , Tomita Shingo 
Published: July 2007

AbstractTo obtain a required document from the uncertain string information inputted by the user in a document retrieval system or an electronic filing system, the string most similar to the inputted string must be searched.This paper assumes the most general case, where no constraint is imposed on the input error and discusses the efficient method of search for the string in the file which is the most similar to the inputted string. The tree structure is considered to be data structure. The string in the file corresponds to the leaf of the tree. Other vertices of the tree correspond to a string constructed from the set of strings below those vertices as a representative element.The classification of the set of strings is made based on the similarity between strings. A simulation is executed using 100 to 1000 English words as the strings in the file. The search probability of the string most similar to the input string, as well as the search efficiency based on the number of similarity calculations, are examined to evaluate the usefulness of the proposed method.
Contour extraction by local parallel and stochastic algorithm which has energy learning faculty
Authors: Hongo Sadayuki , Kawato Mitsuo , Inui Toshio , Miyake Sei 
Published: July 2007

AbstractWhen a combined Markov random field (MRF) image model is applied to the contour extraction problem, the values of parameters specifying the model cannot be known. However, the parameter values can be learned from image examples containing a contour line. This paper first describes details of the learning algorithm. States of line process representing contour line obeys a probability distribution function determined by three aspects: input image, energy function and energy parameters called potential.In the learning algorithm presented here, a value of local potential which specifies an MRF image model is learned using the maximum likelihood method from a contour line image given as a teacher. By applying the proposed learning algorithm to real images, energy parameters are obtained that enable contour extraction that is superior in connectivity and has little noise. Moreover, as a consideration of the generalization faculty of the energy learning algorithm, energy learning for images and extracted contours of images (which are not good for learning) are performed using learned parameters. It was verified that contour lines extracted nonlearning images that are of the same quality as that of contour lines of learning images.
Self‐organizing architecture for learning novel patterns
Authors: Yamauchi Kouichirou , Jimbo Takashi , Umeno Masayoshi 
Published: July 2007

AbstractAlthough the neuron model is very useful for many applications, it has a serious problem of learning. For example, a neuron model for pattern recognition works well after learning, but it must be retrained on all sample patterns if a new category of patterns is added. On the other hand, humans can add the new category immediately, without relearning all the old patterns. To solve this problem, we propose a new self‐organizing architecture for learning novel patterns. This model can learn novel patterns as soon as they are recognized to be new, just like humans do.
Conditions of efficient updates on network structures
Authors: Konomi Shin'Ichi , Furukawa Tetsuya , Kambayashi Yahiko 
Published: July 2007

AbstractRedundant network structures allow efficient retrievals. Procedures to design network structures that allow efficient retrievals [9] add redundancies into network structures. However, as redundancies increase, costs of updates increase. When network structures are redundant, costs of updates include costs of updating original data, checking consistencies, and updating derived data.This paper presents the super‐key condition to reduce the costs of checking consistencies in redundant network structures.First, constraints required to keep redundant network structures consistent are shown and then a sequence of processes to delete or insert a record in redundant network structures maintaining the constraints is given. Relationships between functional dependencies and updates are discussed to derive the super‐key condition. The condition classifies network structures regarding costs of the processes to delete or insert a record. Finally, a procedure to design network structures that satisfy the super‐key condition is given. The procedure may increase redundancies of network structures to reduce costs of updates.