bluuebunny/crossref_metadata_2025_split huggingface dataset:
Organization of the two‐dimensional omega network
Authors: Kumagai Takeshi , Ikegaya Kazuo 
Published: July 2007

AbstractLocal parallel processing is effective for such fields as image processing where problems are essentially two‐dimensional. Here, we propose the two‐dimensional Omega network as an interconnection network suitable for SIMD multiprocessor systems used in such fields. The two‐dimensional Omega network is an interconnection network devised to apply two‐dimensional permutation to local data obtained in parallel from a two‐dimensional array. The structure of inputs and outputs is an N × N two‐dimensional array, and the number of levels is log2N. Here, we will define two‐dimensional permutation as one‐to‐one mapping on the set whose elements are pairs of indices of a two‐dimensional array. Among possible two‐dimensional permutations, are two‐dimensional shift and rotation. We will show the conditions for admissible permutations on the two‐dimensional Omega network. As for hardware, the complexity is N 2/4 m log2N and the delay time is log2N; of the same order as conventional Omega networks. Furthermore, we will discuss the case where the two‐dimensional Omega network has computing capability. We show that sum, maximum, and minimum of elements in two‐dimensional arrays, and two‐dimensional Fourier transformation can be obtained by one pass.
Verification system for partial correctness of communicating sequential processes
Authors: Murakami Masaki , Inagaki Yasuyoshi 
Published: July 2007

AbstractThe communication sequential processes (CSP) system proposed by Hoare is a model for parallel computation which has no shared variables and performs information exchange and synchronization among processes by means of communication commands. In this paper we first consider a set of states for the given CSP program. Using a binary relation on the set, we introduce a semantics representing only the input‐output relations of the CSP program. Based on this semantics, we propose an axiom system which serves to verify the partial correctness of CSP. We prove the soundness of this axiom system. The axiom system proposed in this paper differs from the previously proposed systems in the following aspects. In our system, the inferences proceed simultaneously over all processes. On the other hand, conventional methods adopt a procedure wherein a given property is first proved independently for each process and it is then shown that a certain condition holds among the processes. Our method of proof is a more direct representation of the actual execution of process.
Development of self‐multiplicating compiler writing system
Authors: Hamada Takashi , Masui Toshiyuki , Kayano Yoshiaki 
Published: July 2007

AbstractIn the automatic generation of the compiler, the area requiring further study is the automatic generation of a semantic analyzer. Several methods have been proposed to define the semantics, but a large‐scale description is required. From such a viewpoint, this paper aims at the construction of a compiler‐compiler which can describe the semantics efficiently. A self multiplicating compiler‐compiler (SMCC) was developed by the bootstrap technique used in the development of a new language. SMCC utilizes LL(1) grammar for the syntax analysis and attribute grammar for the semantic analysis. Not only the compiler, but also the SMCC itself can be described. Consequently, the SMCC can successively be extended and an efficient and complex compiler‐compiler can be generated much simpler than by the manual procedure. SMCC is described entirely by C language, and translates the definitions for the compiler or compiler‐compiler into C language. This paper describes the compiler‐compiler SMCC1 which is constructed manually and serves as the initial kernel, and SMCC2 and SMCC3, which are the result of extensions by SMCC1, together with their evaluations.
High‐speed rotation of digital images by raster scanning and table‐lookup operations
Authors: Tabata Kuniaki , Takeda Haruo , Machida Tetsuo 
Published: July 2007

AbstractA high‐speed processing method of rotating two‐dimensional digital images by arbitrary angles is proposed. This method rotates images by combining two skew transformations of raster scanning along X and Y axes. It makes possible group access to horizontally or vertically adjacent pixels in the memory, and shortens memory read/write time per pixel. Each skew transformation includes scale change of images in which the scale factor is approximated by a rational number. The resultant periodicity in transformation is used for high‐speed processing by simple table look‐up operation. The estimated rotation time of images is 250 ‐ 375 ns per pixel with a two‐dimensional memory of transfer speed 1 m̈s/word (1 word = 16 bits) and the pixel shift clock time 125 ns (8 MHz). The scaling error due to rational number approximation depends on the transformation table capacity. The table capacity being 32 or 16 digits, the error is approximately 0.3 or 0.8 percent, respectively. In applying to document image editing, the table of 16 to 32 digits is practically sufficient, implemented by a small number of IC's (about 100). The effectiveness of this method is justified with those examples.
Image data compression based on interpolative dpcm by area decomposition
Authors: Machizawa Akihiko , Tanaka Mamoru 
Published: July 2007

AbstractThis paper proposes a useful method of image data compression which is a two‐dimensional interpolative DPCM, where the mean gray‐scale values of the neighborhood are used as the prediction for the pixel. In the proposed image processing system, the two‐dimensional image is partitioned into subareas in encoding, and the highly correlated subareas in the region are data‐compressed by the interpolative DPCM. A highspeed decoding is realized by calculating the low‐dimensional system of equations by parallel relaxation for the partitioned subareas. The decoding can be executed with the scale of iterative computations required for the analysis of the subarea with the largest dimensions. The architecture of the decoder is suited to the LSI realization, since it can be realized by the bit‐serial adder cell array without using the multiplier‐divider. The encoder has many points in common to the decoder and can be constructed using the same chip. This paper also presents a theoretical evaluation for the compression ratio by encoding and the encoding‐decoding speed in the proposed two‐dimensional interpolative DPCM. A further discussion is made for the three‐dimensional interpolative DPCM for the motion picture. It is shown theoretically that the compression ratio can be made larger utilizing the region‐partitioning of the three‐dimensional space than in the two‐dimensional case with the high‐speed encoding and decoding scheme.
Three‐dimensional reconstruction of torsos by computer and its applications
Authors: Agui Takeshi , Kaneko Yoshikazu , Nakajima Masayuki 
Published: July 2007

AbstractComputer graphics has been applied in the past to the CAD (computer‐aided design) in machine design. However, the technique is recently applied to other fields of industry, and positive attitudes toward CAD are observed in the design of dresses. This paper proposes an algorithm to determine the three‐dimensional structure of torsos from basic dress patterns.A method to reconstruct three‐dimensional objects from dress patterns is described first, and then the algorithm to texture the torsos is described. By the texturing algorithm, it is made possible to choose cloths and design according to individual taste in the form of the completed dress worn on the torso of the customer.
An error detecting and correcting coding method for bilevel images of line drawings using the redundancy of the images
Authors: Minoh Michihiko , Sakai Toshiyuki 
Published: July 2007

AbstractThe development of technology concerning semiconductors and optical fibers now makes image transmission cheaper and more practical. This paper describes an error correcting coding method for binary images of line drawings. First the bilevel images of line drawings are represented by legal patterns, which are defined with a 3 × 3‐pixel unit mesh (window) and employ line constraints. The resulting image is a picture represented by a legal symbol connection (LSC‐picture). This picture includes certain connecting relations among the neighboring legal patterns, which are considered to represent explicitly the redundancy of the original image. Next we encode the picture using a legal pattern as a coding unit. The information source model used for encoding is a simple Markov model. We use line‐to‐line dependencies for the purpose of error detection and correction. When a transmission error is detected by checking the relations, the decoding process generates a tree called an “error correcting tree.” The problem of correcting the transmission error is considered as one of how to search the error correcting tree. The simulation results of this method show that almost all the transmission errors can be corrected if we incorporate a little redundancy of the code words themselves, as in an ordinary method. At the same time, the compression ratio is as high as that of the MR coding method. For image transmission in the future we believe that a description should be considered which can make explicit the redundancy of the image itself as much as possible and that the redundancy should be utilized not only for compressing the amount of data but also for correcting transmission errors.
Defect detection method for stamped patterns utilizing random access parallel matching technique
Authors: Shima Yoshihiro , Kashioka Seiji , Yasue Toshikazu 
Published: July 2007

AbstractIn the fabrication processor of electronic components, the outlook inspection has been performed primarily by visual observation. The automation of this process is presently considered important. This paper describes automatic defect detection considering the stamped pattern on the surface of the electronic parts on the integrated circuit, etc. The only clue to the information on the kind of electronics part is the characters and symbols stamped on its surface. In this sense, the stamped pattern is considered as a part of the part quality. Some defects of the stamped pattern are the disappearance, lack of a part, and dirt. The feature of these defects are discussed first. The fixed‐point sampling is considered which detects the existence of the character pattern at the observation point. The method is modified so that the decision can be made at the observation point along the stroke. Furthermore, a character defect detection system is proposed which can shift the observation point in horizontal and vertical directions so that the system can cope with the variation of the position of the character. A dedicated image processing device was developed to perform the defect detection with high speed. The architecture and the operation of the system are described. The system is advantageous in that the high‐speed operation is realized by the pipeline control for a series of processings, from the parallel read‐out of the local patterns in the image memory to the matching operation. Finally, the configuration of the experimental system is described and the results are shown for the automatic outlook inspection for the stamped pattern of the actual electronic part, thereby indicating the usefulness of the proposed system.
A coding method of line drawings using templates
Authors: Ishii Ikuo 
Published: July 2007

AbstractThis paper proposes a coding method using a template as a highly efficient coding of the line drawing. In the proposed method, the maximum permissible error is specified, and the line drawing with arbitrary curvature is coded within the specified error. In such a case, it is advisable to use the triangular grid for quantization. To improve the efficiency, the direction difference as well as the segment length are simultaneously coded for several links of the triangular grid. Compared with the case of linkwise coding, the number of states to be discriminated is increased in such a shceme, making the coding complex. To simplify the procedure, a template is used to normalize the coding procedure. As a result, the coding complexity can be decreased by 30 to 40 percent, compared with the past direction difference coding using the square grid.
A reducing method for a set of clauses using prepositional formulas
Authors: Nishioka Hiroaki 
Published: July 2007

AbstractIn the resolution‐based theorem proving, logical formulas to be proved are expressed in the form of a closure set (a set of clauses). For proof efficiency, it is desirable that a clause set be reduced to a Horn set by renaming if possible. Several reducing methods have been proposed for this transformation.This paper defines a new reducing method which uses prepositional formulas and is related to a method using 0 – 1 programming. The new method generates a pro‐positional clause set for renaming from the original predicate clause set.A set of logical formulas generated in the method is called a “structural clause set,” because each element in this set indicates the distribution of positive/negative literals in the original predicate clause.An interpretation which satisfies a structural clause set corresponds to a renaming which transforms the original predicate clause set into Horn set.Furthermore, a procedure is presented which determines satisfiability of a structural clause set, and then its time complexity is evaluated.
Fundamental algorithm for train scheduling based on artificial intelligence
Authors: Fukumori Koji , Sano Hiroshi , Hasegawa Toshiharu , Sakai Toshiyuki 
Published: July 2007

AbstractThe trial‐and‐error efforts by experts have been considered as indispensable in compiling railroad timetables. There is a strong requirement to computerize the procedure, but it has been considered difficult. It is proposed to merge the following two concepts as a means to obtain an efficient trial‐and‐error procedure, which is the basis of the compilation of railroad timetables: (1) the concept of (time) belt, where a number of alternatives for arrival and departure is handled as one alternative, considering only the order of arrivals and departures; (2) the concept of the propagation of constraints, which is well known in the artificial intelligence where alternatives in conflict to the order of arrivals and departures are eliminated. This paper discusses the scheduling problem for the partially ordered set of events. The requirement for the time difference between events is considered as a constraint. An algorithm is proposed which calculates the permissible range of time for the event generation, as a closed interval on the time axis. It is shown that the constructed algorithm can be applied as the basic algorithm for the railroad timetable compilation system, where the timetable is considered as a specification for the order of arrivals and departures of the trains, and the arrival‐departure time is considered as a belt. An efficient method of compilating the timetable by the proposed algorithm is presented, based on the search for the possible orders of the trains, together with the construction example of the timetable for the actual railway.
Throughput analysis of reservation protocols with tree‐type reservation channel
Authors: Oie Yuuji , Muro Shojiro , Hasegawa Toshiharu 
Published: July 2007

AbstractNumerous multiple access protocols have been proposed aiming at an efficient utilization of transmission channels. Among those, the tree‐type protocol is one of the multiple access protocols which provide a stable throughput. Various studies have been made on the tree‐type communication protocols. This paper is concerned especially with the analysis of the throughput of the reservation protocols with tree‐type reservation channel. In the proposed system, the tree‐type protocol is employed to reserve the data slot, providing stable and high throughput. There are two types of tree‐type protocols: the blocked‐access tree protocol which inhibits the transmission of a new packet in the collision resolution interval; and the free‐access tree protocol which does not inhibit the transmission. The reservation protocols employing these two protocols are discussed. Through the analysis, the optimum frame structure for each type is obtained. The maximum throughput of CCA proposed by Lee and Mark, as well as the optimum number of the small reservation slots, are obtained analytically.
Response time minimization for processing simple queries in star networks
Authors: Miyao Jun'Ichi , Kikuno Tohru , Yoshida Noriyoshi 
Published: July 2007

AbstractIt has already been shown that the problem of obtaining an optimal strategy for a general query on a distributed database system is NP‐hard. On the other hand, simple queries have been known as one class of queries for which an optimal strategy can be obtained efficiently. So far, it has been shown that if the topology of a computer network is a complete graph, then a strategy with the minimum response time for simple queries can be obtained in O(n2), where n is the number of sites of the network.This paper discusses the problem of obtaining a strategy with the minimum response time for simple queries when the topology of a computer network is a star (in brief, problem RT). We assume that each communication channel of a star network has equal communication capacity, and that each site has an equal capability for data processing. Here, we also assume that the center of a star network is capable of performing so‐called broadcasting. In this paper, we present an algorithm called RT of O(n2) time for solving problem RT. Algorithm RT constructs a schedule graph that represents an optimal strategy by using the dynamic programming method.
Completeness of temporal and spatial logic ETSL
Authors: Iwanuma Koji , Harao Masateru , Noguchi Shoichi 
Published: July 2007

AbstractThe behaviors of such concurrent systems as array processors, should be considered to be a compound interaction of temporal and spatial properties. Thus it is important in expressing semantics to consider both time and spatial axes. However, up to now, few researches have been conducted for a method which treats both axes within the same framework. As a result, previously, we proposed a propositional modal logic ETSL and investigated its model theoretic aspect. In ETSL, the existence theorem of the finite model holds when only finite space is treated. This paper investigates the formal system of ETSL and gives a complete and consistent axiom system for the restricted ETSL which treats only finite spaces. This axiom system is constructed by adding some axioms characterizing time and space to Segerberg's axioms for propositional dynamic logic. Some fundamental operators, e.g., an operator representing “simultaneity,” play important roles in this axiom system. Completeness is proved based on the existence theorem of the foredescribed finite model.
A recognition algorithm of dashed and chained lines for automatic inputting of drawings
Authors: Shimada Shigeru , Kakumoto Shigeru , Ejiri Masakazu 
Published: July 2007

AbstractRecognition of lines in drawings is a major task in automatic data acquisition for CAD (computer‐aided design). This paper proposes an algorithm for the recognition of dashed and chained lines in graphical images. This algorithm consists of two major steps: the local recognition step which extracts local connectivity of line segments, and the global recognition step which performs route finding of connected segments based on syntax. The syntax is usually specific to each type of drawing, and is represented as rules. The performance of the proposed algorithm is demonstrated based on experiments using LSI cell drawings and topographical maps containing dashed and chained lines as graphical components.
Neural mechanisms of information processing in the brain
Authors: Amari Shun‐Ichi 
Published: July 2007

AbstractNumerous researchers have recently become interested in the information processing in the brain. This is because the brain seems to process information in a mechanism which is completely different from that of the computer. The parallel information processing, learning and self‐organizing ability, as well as the memory mechanism of the brain, present interesting principles of information processing which will be very helpful in the design of future computers. To arrive at a clear understanding of those principles, various attempts have been made to describe the underlying principles in a mathematical and systematic way, in parallel to the examination of the behavior of the neural network model. This paper outlines those efforts from the viewpoint of pattern dynamics of the neural field and the visual information processing, learning function in the input‐output characteristics and the control of movement, self‐organization of information recognition mechanism, the associative model, and its stochastic realization. However, this paper aims not only at a review of the present status, but also at pointing out the present problems such as the bottleneck, indicating the problems posed and the direction of the new possible researches.
Sequences of state configurations realizable by the network of a single threshold element
Authors: Miyasaki Kiyonori , Fujino Eiichi 
Published: July 2007

AbstractThe autonomous network composed of a threshold element and n delay elements can be considered as a logical model for the neural network. The discussion of the structure of the state configuration sequences, which are realizable by such a network, will give a clue to the logical operation of the neural network. This paper discusses the state configuration sequences realizable by such a network and the property of the threshold function using the connecting edges and boundary vectors. It is shown first that when the state configuration sequences can only be periodic, the maximum realizable length of the periodic sequences is 2n. Then the self‐dual state configuration sequences are generated from the foregoing state configuration sequences, preserving a certain periodic sequence. It is shown that the network function in this case can be composed of an MBS function, and all boundary vectors and weights and thresholds can easily be determined. The structure of the realizable transient sequences is also discussed.
Distributed algorithms tolerant of link failures
Authors: Masuzawa Toshimitsu , Hagihara Ken'Ichi , Tokura Nobuki 
Published: July 2007

AbstractSo far, numerous distributed algorithms have been proposed. However, most of them do not work well on failure of a processor or link. This paper investigates the relationship between knowledge a processor has concerning the network and the existence of a distributed algorithm under link failure. In this situation, because of the link failure, it is not possible to send a message using it and the processor does not know which link is faulty. The following results are obtained.