bluuebunny/crossref_metadata_2025_split huggingface dataset:
Optimal‐Time Algorithm for the k‐Node‐Connectivity Augmentation Problem for Ternary Trees
Authors: Masuzawa Toshimitsu , Hagihara Ken'ichi , Tokura Nobuki , Wada Koichi 
Published: July 2007

AbstractGiven a graph and a positive integer k, in the k‐node‐connectivity augmentation problem (k‐NCAP), a set of edges is determined to be added to convert the graph into a k‐node‐connected graph with the minimum sum of the added edge‐weights. It is known that 1‐NCAP, for the directed acyclic graph where the weight is restricted to 1 and 2, is NP‐complete. It is also known that when the weight of the edges are all equal, 1‐NCAP for any directed graph can be solved in O([V] + [E]) time, and when the graph is restricted to the directed binary tree, k‐NCAP (k ≥ 2) is solved in O(k |y|) time. In the preceding, |V and |E are the number of nodes and the number of edges of the given graph, respectively. This paper discusses k‐NCAP (k ≥ 2) for the directed graph, where all edge weights are equal. A solution for k‐NCAP is shown for the family of graphs properly containing the directed ternary trees. It is shown that the problem can be solved in (k ≥ 3) time O(k |V) for the directed ternary tree, which is the optimal‐time algorithm within a constant factor. In this paper, a new family of regular and k‐node‐connected graphs called a k‐bouquet is defined. The solution for k‐NCAP is obtained by constructing a k‐bouquet by adding edges to the given graph.
Syndrome‐testable design and syndrome computing method for large PLA's
Authors: Yamada Teruhiko 
Published: July 2007

AbstractNumerous studies have been made on a simplified test method and easily testable circuit design to reduce the test cost of logical circuits. In the syndrome test, which is one of the simplified test methods, all input vectors are applied once each and the number of cases is counted where the output is 1. Consequently, in the application of the method to a large‐scale circuit, it is important to perform the test by partitioning the network into subnetworks of appropriate sizes and to compute the number of syndromes (number of output 1′s) efficiently. This paper discusses the syndrome test for the large‐scale PLA (programmable logic array). The scale of hardware to be added for the syndrome test can be reduced compared with the conventional method. Its construction method is presented. Then an efficient computation method is shown for the syndrome in PLA.
Shape recognition by trial and error processes and its hardware realization
Authors: Nagao Makoto 
Published: July 2007

AbstractThe conventional image analysis methods are far from human‐like recognition methods because they require detailed algorithms for all variations of an image. It is thus desirable to develop a recognition method without complicated algorithms which is as human‐like as possible. Towards this end we propose a shape analysis method involving trial and error processes. We propose a new image processing system using hardware in a top‐down manner. Functions largely realized by hardware are: the placing of a local slit of suitable size in a proper position based on high‐level structural description of the objects, extracting local features by automatic position control and returning the information to higher‐level processing. In this way, users need only describe the structure of an object, and the system can interpret the description and automatically execute structure recognition of objects using the feature extraction mechanism.
Analysis of error‐detecting probability of signature circuit for lsi self‐testing and proprosal of new signature circuit
Authors: Iwasaki Kazuhiko , Yamaguchi Noboru , Hagiwara Yoshimune 
Published: July 2007

AbstractThe self‐testing method using a multiple‐input signature register (MISR) has been proposed as a means of testing logic LSI. This paper analyzes the error‐detecting ability when the MISR is used as a pattern compression circuit. Coding theory technique is applied in the analysis. As the first step, assuming that a Hamming code generating polynomial (primitive polynomial) is used as the polynomial in MISR, the error‐detection rates are determined theoretically for single through quadruple errors. Then the error‐detecting rates for single through quadruple errors are calculated for the modified Hamming code generating polynomial. It is indicated as a result that the multiple error‐detection rate, especially the rate for the double error, does not reach 100%. In order to improve the multiple error‐detection rate, a reversely dual MISR is proposed in which a pair of MISRs is used with opposite shift directions. When the Hamming code generating polynomial is employed as the polynomial in the reversely dual MISR, it is shown that single and double errors are always detected. The rate of triple error detection is calculated. It is also shown that if the modified Hamming code generating polynominal is used, all single, double and triple errors are detected.
Throughput analysis of Tree‐Type protocols
Authors: Oie Yuuji , Muro Shojiro , Hasegawa Toshiharu 
Published: July 2007

AbstractTree‐type protocols achieve stable throughput even under heavy channel traffic compared with random access protocols such as the ALOHA types which show bistable behavior. Various binary tree‐type protocols have been studied extensively for channel stability and the improvement of throughput performance. In this paper, closed‐form solutions of the collision resolution time of several d‐ary tree type protocols are obtained, and the effect of the degree value of their protocols on the throughput performance is discussed. As d‐ary tree‐type protocols, we consider the tree protocol, improved tree protocol, adaptive tree protocol and tree protocol with control mini‐slot, and compare their performance. Further, by comparing the stability of the binary tree protocol with that of three ALOHA schemes with different backoff algorithms, we show that the binary tree protocol exhibits very stable behavior even for a heavy traffic load.
Design of secondary storage system of database machine grace using generalized KD‐tree
Authors: Fushimi Shinya , Kitsuregawa Masaru , Tanaka Hidehiko , Mota‐oka Tohru 
Published: July 2007

AbstractThe relational database machine GRACE can execute heavy relational operations such as joins quite efficiently, thereby resolving the bottleneck in the relational database processing. A new bottleneck, however, is expected to appear at accesses to the secondary storage system. We can also eliminate this new bottleneck by partitioning the database into multidimensional cells adaptively to the access pattern to data. As a result, the average number of page accesses is reduced. We developed an adaptive multidimensional clustering technique called the generalized KD‐tree method. The method is fully adaptive to the access pattern to data and the distribution of tuples. It was shown that the generalized KD‐tree method can reduce the average number of page accesses considerably, even in comparison with other multidimensional clustering algorithms.
Area‐time complexity on a vlsi model with boundary layout assumption
Authors: Wada Koichi , Hagihara Ken'Ichi , Tokura Nobuki 
Published: July 2007

AbstractIn the VLSI circuit, the area occupied by the circuit and the time required for computation are important measures of evaluation. Thompson, Brent and Kung have proposed a VLSI model to evaluate the VLSI circuit by the area A and the computation time T. It is an important problem to examine the change of the area and the computation time when a certain practical assumption is imposed on the VLSI model. This paper shows that when an assumption that the input and the output are connected at the boundary of the circuit (called boundary‐layout assumption) is imposed on the VLSI model, relations AT = ω(max(n, m)) and ATa = ω(max(n, m)[max(log N, log M)]a) (α > 1) are produced for the nontrivial class of n‐input, m‐output logic functions. Above, N is the maximum of N1, …, Nm, where Ni is the number of inputs on which the ith output depends, and Mj is the maximum of M1, …, Mn, where Mj is the number of outputs which depends on the jth input. When the boundary‐layout assumption is not imposed, ATα = ω(max(n, m){max(log N, log M)}α‐1) (α ≥ 1) holds. Consequently, for this class of functions, the boundary‐layout assumption properly affects ATα (α ≥ 1). It is shown also by an actual example that there exist functions which achieve the lower bounds.
Lower bounds on time complexity for some subgraph detection problems
Authors: Arai Masanari , Yamashita Masafumi , Hirata Tomio , Ibaraki Toshihide , Honda Namio 
Published: July 2007

AbstractNontrivial lower bounds of the time complexity are given for a class of problems on graphs. Specifically, given a complete graph with weighted edges, the problem of finding a subgraph satisfying a property π and having edge‐weights that sum exactly to unity is considered. An ω(n3 log n) lower bound is established under the algebraic decision tree model for a property π that satisfies the degree constraint and is closed with respect to isomorphism, where n is the number of vertices in an input graph. This result is a proper generalization of that of Nakayama et al. [8], in which the same lower bound was obtained for π that is hereditary on subgraphs and determined by components. Furthermore, an ω(n3) lower bound is shown for π = “clique” that does not satisfy the degree constraint and hence the above result can not be applied.
An interactive image processing system for microcomputers
Authors: Nagahashi Hiroshi , Nakatsuyama Mikio , Nishizuka Norio 
Published: July 2007

AbstractThis paper considers a symbolic representation of images which is adequate for interactive image processing, and reports an actual system constructed on a minicomputer. The system is closely associated with an LISP. Some attributes of image data and procedures are represented by a frame structure often used in studies of AI or knowledge engineering. Both image data and image processing procedures are managed by frames. Meanwhile, image processing routines can be developed in both low‐and high‐level languages such as ASSEMBLER, FORTRAN or C, and they can easily be linked to the system by specific functions. Consequently, flexible and high‐speed processing can be realized. If some knowledge of image processing is given, this system will be available for fundamental studies of image description and image understanding.
Minimum separation layout for cmos circuits realizing tree‐shape monotone decreasing logic circuits
Authors: Manabe Yoshifumi , Hagihara Ken'Ichi , Tokura Nobuki 
Published: July 2007

AbstractIn CMOS circuits transistors in a p‐MOS circuit and n‐MOS circuit that have a common gate input are often placed next to each other. In such a case, if adjacent diffusion areas are of the same potential, it is possible to merge them to reduce the circuit area. Therefore an important problem is how to obtain efficiently a circuit layout with the minimum number of places (separation) where the merge is impossible. At present, it is known that the minimum separation is zero in a tree‐shape monotone decreasing logic circuit when the fan‐in number of each logic element is odd. However, the time complexity for obtaining the minimum separation for a given arbitrary circuit has not been reported yet. This paper shows that the following problems can be solved in a time linear to the sum of the number of the logical variables and the number of the logic elements where k or h is a constant when a tree‐shape monotone decreasing logic circuit C and a nonnegative integer k are given, determining whether or not there exists a layout of C having separation k or less. If one exists, obtain the minimum separation and a layout with the minimum; and obtain the minimum separation and a layout with the minimum when the fan‐in of each logic element of C is h or less.
Performance evaluation of the binary tree access mechanism in mimd type parallel computers
Authors: Sueyoshi Toshinori , Saisho Keizo , Arita Itsujiro 
Published: July 2007

AbstractOne of the most serious problems in a highly multiple parallel processing system involves memory access contention. In the hierarchically structured access mechanism, the number of simultaneous access paths increases with degree of parallelism. Consequently, it is considered as a configuration suited to a highly multiple parallel system. This paper uses a queue model to analyze the hierarchical routing bus (H‐R bus), which is an access mechanism with a hierarchical structure. The paper further makes a quantitative evaluation of the locality in data access. Based on the derived theoretical expressions and measured results obtained by executing several test programs on the H‐R bus‐connected parallel computer, the H‐R bus performance is evaluated. The results obtained in this paper are as follows: (1) Low external data access rates (i.e., external data access time/processing time) indicate that the H‐R bus‐connected multiprocessor system operates with high efficiency even under high multiplicity. (2) Under sufficient access locality, even high external data access rates do not unduly impair efficiency. Although the above properties have qualitatively been known before, this paper derives theoretical expressions for the properties, supported by experiments.
Event‐driven relaxation method based on asynchronous parallel processing
Authors: Kato Toshikazu , Sakai Toshiyuki 
Published: July 2007

AbstractThe application of the relaxation method to image processing was proposed by Rosenfeld et al. and has been applied in actual problems. One of the problems in the relaxation method concerns computational complexity, where a uniform processing is applied to all objects in each iterative step. From such a viewpoint, the processing speed should be improved. This paper proposes a region‐growing relaxation method, which is an event‐driven relaxation based on asynchronous parallel processing mechanism, and can be applied to the object for which the interpretation should be modified. From the viewpoint of our transformation model representation, the performance of the relaxation method is analyzed. The relaxation model presented by Rosenfeld corresponds to the fixed‐mean oriented procedure for the object, while the proposed model corresponds to a region‐growing one, where the objects of processing are grouped together. The notion of event and eventdriven processing mechanism is introduced into the pattern information processing, and it is shown that the region‐growing relaxation exhibits a high processing efficiency. The region‐growing relaxation is an extension of the discrete model by Rosenfeld, and has the following features: (i) The convergence (termination) is achieved by a finite number of repetitions; (ii) Asynchronous parallel processing can be adopted; (iii) Algorithm is suited to the eventdriven processing; (iv) The convergence is fast compared with the fixed‐mean oriented relaxation; (v) Region segmentation is achieved at the same time. The region‐growing relaxation method is presently adopted in the newspaper layout understanding system EXPRESS.
Reliability evaluation of partitioned TMR systems
Authors: Izawa Nobuyoshi 
Published: July 2007

AbstractThe fault‐tolerant technique has been frequently employed to realize a highly reliable computer system. This paper considers the Triple‐Modular Redundancy (TMR) system, which is one of the fault‐tolerant systems whereby the system is partitioned into several blocks and the majority decision is made in each block. The reliability of such a system is evaluated. Based on the relation between the number of partitions and the failure rate of such a system, the following two types of models are assumed:(1) TMR network model, where the failure rate of the whole system increases with the number of partitions, when the failure rate of the block is kept constant.(2) LSI model, where the block failure rate decreases with the number of partitions, when the failure rate of the whole system is kept constant. Especially, in the model (2), the pin‐gate ratio of LSI is taken into consideration. For these models, the expression for the Mean‐Time‐To‐Failure (MTTF), which is the mean operation time until a system failure occurs, is derived. The general tendency of MTTF is analyzed. By numerical examples, the improvement of MTTF by partitioning is demonstrated. The improvement of the TMR system by partitioning is demonstrated quantitatively.
Attenuation correction for infrared rays emission CT
Authors: Uchiyama Hiroki , Kazahaya Kanji , Nakajima Masato , Mizomot Masahiko , Yuta Shinichi 
Published: July 2007

AbstractWe have already proposed the infrared rays emission CT (IRECT) as a method to visualize the temperature distribution inside the flame. IRECT is a method of visualizing the infrared ray source intensity distribution inside the flame in the form of a cross‐sectional image, by numerically processing the one‐dimensional projection data obtained by the external noninvasive measurement of the infrared rays emitted from the flame. Since IRECT is an emission‐type CT, the method contains a problem in that the image quality is degraded by the attenuation of the infrared ray. The correction of the attenuation must be considered for a highly accurate measurement. This paper discusses the application of the attenuation correction method (DMF method) to IRECT, which was recently developed for the application to the gamma ray CT. The result of experimental verification is also presented. A new measurement method is presented for the attenuation coefficient distribution inside the flame, which is needed in the application of the attenuation correction method.
Automatic generation of syntax‐directed editor
Authors: Hamada Takashi , Miyauchi Hiroshi 
Published: July 2007

AbstractThis paper describes the development of the syntax‐directed editor generator system (GED). The earlier syntax‐directed editors have some unsatisfactory points from the viewpoint of the user interface. The editor constructed by GED should realize the following three functions in order to improve the user interface: (1) top‐down programming is possible using the command template; (2) the delete, insert and replace of character strings can be made as the text editor; (3) the command defined by the user can easily be used. Giving the inputs such as syntax rules of the object programming language, the editor of that language is produced. For editing as texts, the incremental parser must be constructed in the generation of the editor. For this purpose, the incremental look‐ahead LR(1) (ILALR(1)) is proposed and applied which is an extension of the early parser.
Construction of a software development environment based on a high‐level language architecture
Authors: Tsubotani Hideaki , Tenma Takao , Tanaka Minoru , Ichikawa Tadao 
Published: July 2007

AbstractIn software development it is becoming more important to offer an environment which helps decrease software cost and increase productivity and reliability. On the other hand, for program coding, different programming languages are used depending on the application fields of newly developed software systems. Thus, we must prepare a dedicated development environment for each programming language. Moreover, when we realize a language processing system for a programming language which has high descriptive capability such as Ada, a problem arises on how to achieve appropriate load distribution between software and hardware. From such a viewpoint, we have developed a high‐level language architecture SPRING for language classes such as Ada and Pascal. SPRING performs run‐time checks at the architecture level, for example, checks indices of arrays, the value range of subtype variables, etc. Further, we constructed a software development environment EDMAS on a computer based on this architecture as a concrete example of a software development environment. EDMAS aids in developing in a top‐down fashion, a software system in case Ada is used. This paper describes the high‐level language architecture SPRING and the software development environment EDMAS.
Hierarchical coding of line—Drawing data described by the chain—Code sequence
Authors: Kaneko Toru 
Published: July 2007

AbstractA hierarchical encoding scheme has been proposed to realize efficient coding of line‐drawing data described by the chain‐code sequence. For links, each of which is an ordered pair of succeeding grid points in the sequence, the encoding scheme builds up a pyramid‐like code structure by uniting links by twos, and it has the following advantages:1) line drawing can be decoded in various scales (power of 2s);2) high coding efficiency is obtained for each layer; and3) degradation in display quality due to a blot‐like effect in small‐scale layers is relaxed.Concerning the coding efficiency in item 2), an experiment using coastline data obtained from a topographical map gave the coding rate for each layer of about 1. 1 bits/link. This shows that the proposed scheme is more efficient than data filing by independent encoding of each scale data.
Topological patterns of synchronization in the biological oscillator
Authors: Akamatsu Norio 
Published: July 2007

AbstractThis paper presents a mathematical model for the biological oscillator with external stimulus such as cardiac pacemaker, and analyzes the synchronization phenomenon. The system to consider is described by a nonlinear differential equation. A simulation is made to examine the details of the synchronization and desynchronization. In the paper, the idea of Poincare's mapping is applied to examine the relation between the invariant set on the topological plane and the synchronization. As a typical example of arrhythmic phenomenon, the amplitude and the frequency of the external stimulus is varied to determine the entrained region for the 1/2‐harmonic oscillation. The transition among various synchronization patterns appearing in this region can be accounted for by the spatial relations among the stable and the unstable manifolds. It is shown as a result that when the locations of the stable and unstable manifolds are interchanged, they intersect, leading to the homoclinic or heteroclinic points. A random rhythm has been observed in the escape phenomenon of the cardiac pacemaker, and the chaotic random oscillation is also derived from the mathematical model. It is shown that the origin of the chaos is related to the heteroclinic and homoclinic structures.
Interpretive process of depth in line drawing
Authors: Kawabata Nobuo 
Published: July 2007

AbstractThe Necker cube is a line drawing having two possible solutions in depth perception. The process of interpreting a two‐dimensional line drawing as a three‐dimensional object was investigated using the Necker cube. Attention was directed to a local feature of a briefly presented cube, i.e., an angle at a vertex. The angle under observation was perceived as a front part of the cube and other parts were interpreted so as to match the interpretation of the angle pattern. Results show that the local feature to which attention was directed, was interpreted first. Then global features and other local features were interpreted so as to agree with the local feature interpreted initially. This suggests that the three‐dimensional interpretation of the line drawing was made sequentially from the local feature to global structures.