|
1. |
Verification system for freedom from deadlock of communicating sequential processes |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 1-10
Masaki Murakami,
Yasuyoshi Inagaki,
Preview
|
PDF (600KB)
|
|
摘要:
AbstractThe communicating sequential processes (CSP) proposed by Hoare are a model for parallel computation in which the processes do not share a variable and perform the interprocess information exchange and synchronization by the communication instruction function. This paper first extends the verification system for the partial validity of CSP previously proposed by the authors and an axiomatic system is presented by implementing part of the inference rules which can deal with the deadlock‐free property of CSP. The soundness of the system is shown. The system previously proposed by the authors can provide the inferences in a concurrent way independently of the processes, without following the sequential procedure of proving a property for a process and proving a certain relation between processes. The system proposed in this paper employs a similar procedure and verification is made in parallel for the partial validity and deadlock‐free property of
ISSN:0882-1666
DOI:10.1002/scj.4690180401
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
2. |
Response time minimization for processing simple queries in star networks |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 11-23
Jun'Ichi Miyao,
Tohru Kikuno,
Noriyoshi Yoshida,
Preview
|
PDF (849KB)
|
|
摘要:
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 inO(n2), wherenis 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 ofO(n2) time for solving problem RT. Algorithm RT constructs a schedule graph that represents an optimal strategy by using the dynamic programming met
ISSN:0882-1666
DOI:10.1002/scj.4690180402
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
3. |
Matching of distorted central symmetry image—An application to seal impression collation |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 24-32
Haruo Takeda,
Kuniaki Tabata,
Toshihiro Hananoi,
Preview
|
PDF (636KB)
|
|
摘要:
AbstractThis paper considers the pattern matching of images in which, originally, the boundary has central symmetry which is made incomplete by defects and noises. A detection method for the centroid of symmetry is proposed. In the proposed method, the boundary is rotated by 180° to match itself (self‐matching of the boundary), thereby detecting the centroid by utilizing all position information of the pixels on the boundary. When the defects are assumed, methods such as tracing cannot be applied directly to the extraction of the boundary, and a simple scheme is employed which scans the image in parallel to the coordinate axis. The effect of the spurious information produced by the scanning is eliminated by using the histogram as the measure of the boundary matching. The effect of the missing information is eliminated by superposing the histogram, which is obtained by scanning in the direction perpendicular to the original scanning, to the original histogram. The proposed method is applied to collation of seal impressions. It was verified that the positioning is performed within the error of one pixel for the ordinary defect of the impression frame and the partial defect of the frame due to the noise by background and fibrous padding material. It was also verified that a processing with practically sufficient speed can be realized. The proposed method will also be applied effectively to the positioning of the images with partial central symmetry, such as a circular component with a protrusi
ISSN:0882-1666
DOI:10.1002/scj.4690180403
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
4. |
Three‐state neumann neighbor cellular automata capable of constructing self‐reproducing machines |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 33-40
Teruo Serizawa,
Preview
|
PDF (478KB)
|
|
摘要:
AbstractThis paper defines the 3‐state Neumann‐neighbor cellular automata, and shows that its space is construction‐universal. The proof for this is achieved by presenting a realization of self‐reproducing machines. The state‐transition rule and the basic operations of configurations of the cellular automata are described first. Then methods are shown to construct AND circuit, pulse generator, signal‐line, delay circuit and memory circuit. Finally, the structure of the self‐reproducing machine is shown, which is realized by combining those circuits, The machine has two construction arms, a Turing tape and a timing loop. It can make a replica of its own using the Turing tape. The machine can also be operated as a universal construction machine or a universal T
ISSN:0882-1666
DOI:10.1002/scj.4690180404
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
5. |
Design of VLSI‐oriented radix‐4 signed‐digit arithmetic circuits using multiple‐valued logic |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 41-52
Shoji Kawahito,
Michitaka Kameyama,
Tatsuo Higuchi,
Preview
|
PDF (833KB)
|
|
摘要:
AbstractRadix‐4 signed‐digit (SD) arithmetic circuits using multiple‐valued logic are proposed from the viewpoint of VLSI implementation. Because of the property of sign‐symmetry in the SD number representation, a new bi‐directional current‐mode MOS technology is employed very effectively in implementing very fast and compact SD arithmetic circuits. These basic operations are simulated and evaluated using SPICE2. Finally, it is demonstrated that these arithmetic circuits can be fabricated using 2 um CMOS technology. For example, a multiply time of 40 ns can be achieved in the SD multiplier with a 17 × 16 b
ISSN:0882-1666
DOI:10.1002/scj.4690180405
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
6. |
Hierarchical coding of line—Drawing data described by the chain—Code sequence |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 53-63
Toru Kaneko,
Preview
|
PDF (679KB)
|
|
摘要:
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 s
ISSN:0882-1666
DOI:10.1002/scj.4690180406
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
7. |
Computer classification of rosette‐forming cells from microscope images |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 64-75
Hiroki Ohta,
Shinji Ozawa,
Minami Miyauchi,
Hajime Takata,
Akira Sonoda,
Hisami Iri,
Preview
|
PDF (889KB)
|
|
摘要:
AbstractThis paper presents a method of rosette‐forming cell classification by image processing. This method is useful in the field of clinical immunology in dividing lymphocytes into some subpopulations and quantifying each component. The “Rosette Formation Test” is one of the most popular methods of classifying lymphocytes which consist of the different functional subsets. However, the rosette‐nonrosette judgment has been done by a human expert using a microscope. Considerable manpower is needed to judge rosette/non‐rosette cells. To solve this problem, we present a computer classification system of rosette‐forming cells in the microscopic image. The system constructs an accumulative gray‐level histogram for each cell, extracts features from histograms, and then classifies cells with the discriminant function.To confirm the effectiveness, we examined the classification system for several images. As a result with learning data (991 cells), the accuracy of classification is 84.5 percent, and the correct rate of resetted and nonrosetted cells is 86.6 percent. With unknown data (509 cells), the accuracy of classification is 84.1 percent, and the correct rate of resetted and nonrosetted cells is
ISSN:0882-1666
DOI:10.1002/scj.4690180407
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
8. |
Extraction of Nth‐order features of line patterns considering redundant information |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 76-85
Norifusa Nishiyama,
Kazuo Inoue,
Preview
|
PDF (673KB)
|
|
摘要:
AbstractThe extraction of geometric features is a basic and significant process for pattern recognition. This paper proposes a method of extracting geometric feature by referring redundant information around the feature point.For written or oral information, even if some information is unable to be understood, we can infer meaning by knowing redundant information. Using the same principle as mentioned in the opening paragraph, this paper introduces a method to extract the geometric feature by detecting redundant information around the feature point.Finally, to verify the usefulness and effectiveness of this method, computer simulation experiment is performed on test patterns and handwritten numerals.
ISSN:0882-1666
DOI:10.1002/scj.4690180408
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
9. |
Topological patterns of synchronization in the biological oscillator |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 86-100
Norio Akamatsu,
Preview
|
PDF (1104KB)
|
|
摘要:
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 structure
ISSN:0882-1666
DOI:10.1002/scj.4690180409
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
10. |
A method of document‐image segmentation based on projection profiles, stroke densities and circumscribed rectangles |
|
Systems and Computers in Japan,
Volume 18,
Issue 4,
1987,
Page 101-111
Teruo Akiyama,
Isao Masuda,
Preview
|
PDF (860KB)
|
|
摘要:
AbstractA method is proposed wherein printed documents are segmented into the following three areas: headline area, textline area, and attached area. Then the character lines constituting headline and textline are extracted. This paper describes: 1) the combination of the global features of the document such as projection profiles and stroke densities, and the local features of the document such as circumscribed rectangles are used; 2) the basic features of document elements such as character line periodicity in the textline area, so that a single method can be applied to segment document elements in differently formatted documents.An experimental result of this method applied to eight Japanese and English printed documents of both horizontal and vertical lines showed that 98.4 percent of the headlines in headline area, 99.9 percent of the textlines in textline area, and 83.3 percent of diagrams in the attached area were segmented successfully.The result confirms that this method is effective in segmenting document elements, and applicable to a variety of documents. Part of document processing is implemented in the experiment by special hardware for speed.
ISSN:0882-1666
DOI:10.1002/scj.4690180410
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1987
数据来源: WILEY
|
|