摘要:

AbstractThis paper proposes a new algorithm MAXCLIQUE which finds a maximum clique in an undirected graph withnvertices, and shows that its worst‐case time complexity isO(2n/2.863). For the dual problem of finding a maximum independent set of vertices, Tarjan et al. already have proposed an algorithm of worst‐case time complexityO(2n/3) [2]. However, by comparison, our algorithm is remarkably simpler, and it was confirmed that it runs faster when two algorithms were used for several random graphs and their average running times were measu

ISSN:0882-1666    

DOI:10.1002/scj.4690210301

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractThe aim of this study is to apply the unprecedented high‐speed computing made possible by parallel processing to a wide range of problems such as computer graphics. A highly parallel cellular array processor, the CAP‐256 has been developed in which 256 high‐performance processors, called cells, are connected together. The CAP‐256 includes a function by which a generated image is displayed in real‐time, as well as a function to construct various kinds of [inter‐processor] communication networks (topologies). A VLSI chip has been developed which integrates the communication and synchronization functions required for parallel processing, as well as the I/O function for the image. Using this VLSI chip, the cell was implemented in a compact form, and a small‐sized high‐performance parallel computer was implemented.To operate the cell, software called the cell OS (operating system) was developed. The software environment which has been implemented makes it possible to easily develop and efficiently execute application programs based on message communication. An image was generated using parallel ray‐tracing which has three to four times higher performance than that of the general‐purpose FACOM M‐380 mainframe computer. The authors are also attempting to develop applications for CAD problems such as automatic wiring as well as scientific calculations. The versatility of the CAR

ISSN:0882-1666    

DOI:10.1002/scj.4690210302

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractThis paper proposes a reconstruction method for the 3‐D distributional image of the absorption coefficient of the object. In the method, a cone‐beam X‐ray source and a 2‐D detector array are placed in confronting positions on the opposite sides of the object. By rotating them 360 deg., the projection data are acquired, and then the inverse filtering is applied. This is a reconstruction problem from an incomplete projection data.In this paper, the compound image is constructed by backprojecting the projection image directly along the locus of projection. The inverse filtering is applied to the result to determine the 3‐D distribution image of the absorption coefficient of the object. In the defined geometrical system for the measurement, the inverse filtering cannot essentially be applied since the impulse response is space variant. Consequently, a nonuniform sampling coordinate system is defined to make the impulse response space invariant.The inverse filter function is derived from the Hankel function by utilizing the symmetry of the impulse response in regard to the axis of rotation. Furthermore, to stabilize the inverse filtering, a window function is employed which considers the space‐dependence of the incompleteness of the projection image in the frequency domain. Finally, the usefulness of the proposed reconstruction method is verified by a computer

ISSN:0882-1666    

DOI:10.1002/scj.4690210303

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractThe high‐dimensional grammars, such as Plex grammar and graph grammar, have strong descriptive powers, but have a problem in that the parsing algorithm is difficult. To apply those grammars to the pattern analysis and recognition, it is desirable that the parsing method for those grammars should be established. As a method toward the parsing of Plex grammar, the authors previously have proposed a C‐Plex grammar and a parsing method for the context‐free C‐Plex grammar, based on the logic programming of Prolog. Further, a parsing method is presented for context‐sensitive C‐Plex grammar based on the logic programming.First, a parsing algorithm is proposed which realizes the pseudo‐leftmost derivation in context‐sensitive C‐Plex grammar. Then, to arrive at a Horn clause program executing the parsing algorithm, a general rewriting method from the context‐sensitive C‐plex grammar to Horn clause is presented. Using the circuit pattern as an example, the result of parsing is shown. The description of rules by predicate logic expression and the parsing method based on logic language Prolog characterize the C‐Plex grammar as a kind of logic grammar. C‐Plex grammar can be applied not only to the grammatical pattern analysis and recognition but also to the parsing processing in the intelligent system such as pattern interpre

ISSN:0882-1666    

DOI:10.1002/scj.4690210304

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractLocal area networks (LANs) such as Ethernet provide cheap, high‐speed communications. Here we present a new high‐speed local area network model in which the LAN is configured with node‐processors which halt and/or recover asynchronously. We also propose an algorithm for dealing with the problem of information‐updating with a proof of the correctness of the al

ISSN:0882-1666    

DOI:10.1002/scj.4690210305

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractThis paper proposes a new universal fault‐tolerant hypercube architecture. This architecture is obtained by constructing a basic fault‐tolerant hypercube and expanding it using the product of graphs. The basic cube is constructed by partitioning all processing elements (PEs) into subsets with weak connectivity using the Hamming distance between PE numbers and by connecting all PEs in each subset to a spare PE through buses. This architecture can maintain the original network topology and size without the addition of any switching hardware and can be applied to any size hypercube. Moreover, because the number of spare PE ports is equal to or fewer than the number of original PE ports, the same kind of PE can be used for both original PEs and spa

ISSN:0882-1666    

DOI:10.1002/scj.4690210306

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractRecently, there has been active research on image recognition technology using computers. It is necessary for image recognition to extract some elements automatically, such as straight lines, circles, numerical letters and symbols from a picture. There are many cases where the extraction of such elements is not easy because some overlap others. This paper describes a method of extracting overlapped elements separately from a binary picture.The method can extract an element which has a constant shape with arbitrary size or rotation angle, or with both an arbitrary size and an arbitrary angle. Also, it uses both a single key point and several feature points on the model of a figure to be processed. The extraction is carried out by checking if there are several pixels corresponding to the feature points, when each pixel is regarded as a key point of the model.This paper describes the algorithm of the method, a method of extracting some important straight lines and circles in the picture using the algorithm, and experimental applications of the method to mechanical drawings. The results of the experiments demonstrate a successful extraction of straight lines, circles, arrows, and numerical letters, and this confirms the usefulness of the proposed method.

ISSN:0882-1666    

DOI:10.1002/scj.4690210307

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractConventional concurrency control schedulers are used to increase concurrency to avoid transaction rollbacks, and it is widely accepted that a scheduler is effective if it can provide more concurrency. However, transaction rollbacks seldom occur in a practical transaction processing system. The performance of a scheduler should be evaluated by how efficient a schedule it can generate in such a situation. We select the number of secondary storage accesses to process a given schedule as such an efficient criterion.A schedule is regarded as a page reference string and the memory cost of the schedule is defined by the cost to process the schedule by an optimal paging algorithm. Then we consider the minimum memory cost scheduling problem for a given set of transactions. The problem is shown to be NP hard in the general case. Thus we turn our attention to: (1) a restriction of the transaction model to construct an optimal schedule in a linear time; and (2) a nearly optimal solution to the given problem under a general transaction model. The nearly optimal scheduling problem is shown to be rather difficult.

ISSN:0882-1666    

DOI:10.1002/scj.4690210308

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractA unified coding method of image and text data is proposed in this paper. This scheme enables us to embed a text into an image by using some redundant region in the frequency space. Our results show that a text of about 4 k to 8 kbytes can be embedded into the image of 256 × 256 pixels and it retains an S/N ratio of about 30 to 40 dB

ISSN:0882-1666    

DOI:10.1002/scj.4690210309

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY

摘要:

AbstractForp‐valued synchronous sequential machines a new method of state assignment is proposed. In this method, a given sequential machine is expressed by a state transition table and then codes with low Hamming weight are assigned to the internal states with high frequency of appearance. This process yields the state transition functions which express transition to the states with low frequency of appearance, thereby attaining the state transition functions with the minimum number of terms in the principal disjunctive canonical form. All the procedures can be expressed in a simple straightforward algorithm and therefore can be processed fast. Experiments on a computer forp= 3 show that the truth‐table densities of the state transition matrices are about 80 to 90 percent compared with those obtained by the triangle method [1, 2] which is one of the existing methods. The results compare favorably with those obtained by other methods even after simplification by the extended Quine‐McCluskey m

ISSN:0882-1666    

DOI:10.1002/scj.4690210310

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1990

数据来源: WILEY