摘要:

AbstractThis paper presents the basic idea in the design of the data‐flow language DFC and problems and their solutions in its implementation on the data‐flow computer SIGMA‐1. DFC is a data‐flow language designed with consideration of the compatibility to C language. In the first part of the paper, a design to integrate the functional properties while maintaining the compatibility to C language is shown for the conditional and loop sentences, which are the major components of DFC, as well as the data structure. Then the conversion procedure from DFC to the code of SIGMA‐1 is described together with the problems and their solutions.Especially, the generation of a graph is discussed in detail, which enables the resource reclamation in execution with the data‐flow compu

ISSN:0882-1666    

DOI:10.1002/scj.4690200601

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

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper discusses the basic properties of the probabilistic push‐down automaton (PPDA). Intuitively speaking, PPDA is obtained by adding a probabilistic property to the nondeterministic transition of the nondeterministic push‐down automaton (NPDA). According to the property of the error in the accepting condition, PPDA is classified into a two‐sided error PPDA, a one‐sided error PPDA, and bounded error PPDA. Moreover, the acception error is considered not only for 1/2, but also for an arbitrary cut‐point, to discuss the relations among classes of languages. Major results are as follows.The class of languages accepted by bounded error PPDA is not the same as that accepted by NPDA. In the case of two‐sided error PPDA and the bounded error PPDA, the class of acceptable languages does not depend on the cut‐point. In the case of a one‐sided PPDA, the class of acceptable languages depends to some extent on the cut‐point. In other words, there exists an infinite hierarchy. Kolmogorov complexity is used in the proof of

ISSN:0882-1666    

DOI:10.1002/scj.4690200602

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

年代:1989

数据来源: WILEY

摘要:

AbstractIt is well known that the use of the high‐level information data such as language information is indispensable in the speech understanding system. Because the human speech understanding process is executed unconsciously, sufficient knowledge is not yet available concerning what kind of high‐level information data are utilized and in what ways. We made two kinds of studies from the viewpoint of cognitive science to acquire knowledge about the use of high‐level information. Based on the result of study, an association based parser ASP was realized for the speech understanding system. ASP receives a large number of phrase candidate sequences as the input, and identifies the correct phrase sequence by examining successively the available syntactic, semantic and associative information. Especially, the topic is extracted first from the input candidates as a whole, and an association mechanism is employed where the vocabulary associated from the topic is processed with priority, being considered as an active word. The study in this paper is described from the viewpoint of cognitive science, and the framework of the language processing system obtained from the study is pres

ISSN:0882-1666    

DOI:10.1002/scj.4690200603

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

年代:1989

数据来源: WILEY

摘要:

AbstractIn language processing aiming at speech understanding, not only knowledge about the syntax and the semantics, but also knowledge about the context and the control play important roles in dissolving the ambiguity due to the uncertainty in the phoneme recognition. This paper discusses the association‐based parser ASP. Discussions are made especially on the details of the employed knowledges and the result of evaluation experiment, which was performed to verify the usefulness of the association mechanism. In ASP, based on the semantic memory, episode memory, syntactic knowledge and control knowledge, the vocabulary associated with a topic in the sentence is processed with priority, and the control of the search in the intelligent backtrack is performed. In the evaluation experiment, the control knowledge to determine the object of processing from the contending partial solutions, as well as the effect of the order of solution candidates in the phrase, are particularly examined. It was verified as the result that ASP exhibits a performance independent of the order of the solution candidates under a pertinent control strategy, and the correct phrase sequence is identified, based largely on the syntactic and semantic informations, even if there does not exist an appropriate topi

ISSN:0882-1666    

DOI:10.1002/scj.4690200604

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

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper considers multiple context‐free grammars (mcfg's) which inherit the basic properties of context‐free grammars with generative capacity stronger than that of context‐free grammars but weaker than that of context‐sensitive grammars. It is shown that the time complexity of the membership problem for languages generated by mcfg's is polynomial. It is shown also that head grammars introduced by Pollard for describing the syntax of natural language correspond to a special subclass of mcfg's and, as a corollary, the time complexity of the membership problem for languages generated by head grammars is of ordern6.* This is an improvement by one order of magnitude, compared with the result by

ISSN:0882-1666    

DOI:10.1002/scj.4690200605

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

年代:1989

数据来源: WILEY

摘要:

AbstractOften, partial differential equations for the case of numerical computation are solved. However, to solve partial differential equations whose order of dimensions are more than 2, main memory is not large enough even in the main frame or super computers, not to mention workstations or personal computers. Thus, we have to use external memory to solve large partial differential equations numerically. This paper proposes an algorithm to solve numerically by explicit methods, large partial differential equations which are time‐dependent and have fixed boundary conditions. In this algorithm, neighbor mesh points are placed together in main memory. Also, even partially, they are computed toward the time axis as far as possible. In other words, this method computes mesh points toward the time axis with priority, reusing computed data in main memory. The proposed algorithm is unique in this point. It is faster than conventional methods in proportion toD√PwherePis the bulk of the main memory andDis the order of dimensi

ISSN:0882-1666    

DOI:10.1002/scj.4690200606

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

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper presents a state analysis of multiprogramming, using the concept of cusp catastrophe in the theory of catastrophe. Based on the result, the catastrophic phenomena in the multiprogramming system are analyzed. It is shown first that the multiprogramming system exhibits two stable states, i.e., monostable and bistable states, for the change of job generation rate and the change of the maximum multiprogramming level. Then it is shown that a rapid change (catastrophe) of the performance of the multiprogramming system, such as the mean number of jobs in the system, throughput and response time, may occur with the change of the stable state of the system. Furthermore, it is shown that for any given job generation rate, there exists a maximum multiprogramming level which maximizes the throughput and minimizes the response time.

ISSN:0882-1666    

DOI:10.1002/scj.4690200607

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

年代:1989

数据来源: WILEY

摘要:

AbstractFor highly parallel operation, use of a radix‐4 signed‐digit (SD) number system is attractive. Since the SD number system uses more than three values in each digit, multivalued coding is suitable for the implementation of the high‐speed compact arithmetic integrated circuits. We have already proposed the basic idea of multivalued bidirectional current‐mode circuits which are essentially suitable for the SD arithmetic implementation. This paper describes the experimental results of the basic SD arithmetic integrated circuits by means of the bidirectional current‐mode circuits and their evaluation. A parallel SD adder is implemented with 2‐μm CMOS technology and the addition time is estimated to be about 10 ns. The addition time of the SD adder is 14 times faster than that of the conventional ripple‐carry adder and is three times faster than that of the block carry l

ISSN:0882-1666    

DOI:10.1002/scj.4690200608

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

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper presents an approximate solution for the process assignment problem with communication contentions in the distributed system. It is assumed that several processes perform a job through mutual communication, and that the process knows the interprocess communication probability as well as its mean interval. A method is shown in this paper whereby the distributed system is modeled as a queueing network model, and the mean job execution time is determined analytically. Then assuming that the job is composed of several such processes, an approximate solution is shown based on the branch‐and‐bound method to derive the assignment to processors minimizing the mean job execution time. Several methods are introduced to reduce the search time. Finally, based on numerical examples, it is demonstrated that the proposed method is sufficiently useful with a small error compared with the exact solut

ISSN:0882-1666    

DOI:10.1002/scj.4690200609

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

年代:1989

数据来源: WILEY

摘要:

AbstractThe rotation of an image is one of the fundamental functions in image processing and is applied to document image processing in the office or for industrial use with industrial robots. A method of image rotation based on digital image data has been developed. This paper assumes the binary digital data, and proposes a method which is different from the traditional one based on pixel data. This method can execute a high‐speed rotation of the binary image based on coordinate data for the start and the end of the run. Using the proposed method, the image rotation at an arbitrary angle can be realized by the real number operation on the run data, which is suited to the general‐purpose processor. It is a practically useful method since the processing is fast and less memory capacity is required. In this paper, a discussion is made first on the format of the run data, the number of runs and the data complexity for the binary data. Then the newly devised rotation for the binary image is described. The rotation method is used to perform successively the skew coordinate transformations in the vertical and horizontal directions, to determine the rotated image. Finally, a document image is actually rotated on a large‐scale computer. The processing time was examined to demonstrate experimentally the usefulness of the proposed m

ISSN:0882-1666    

DOI:10.1002/scj.4690200610

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

年代:1989

数据来源: WILEY