Numerous studies have so far been carried out extensively for the analysis of document image structure, with particular emphasis placed on media conversion and layout analysis. For the conversion of a collection of books in a library into the form of hypertext documents, a logical structure extraction technology is indispensable, in addition to document layout analysis. The table of contents of a book generally involves very concise and faithful information to represent the logical structure of the entire book. That is to say, we can efficiently analyze the logical structure of a book by making full use of its contents pages. This paper proposes a new approach for document logical structure analysis to convert document images and contents information into an electronic document. First, the contents pages of a book are analyzed to acquire the overall document logical structure. Thereafter, we are able to use this information to acquire the logical structure of all the pages of the book by analyzing consecutive pages of a portion of the book. Test results demonstrate very high discrimination rates: up to 97.6% for the headline structure, 99.4% for the text structure, 97.8% for the page-number structure and almost 100% for the head-foot structure.

The authors propose a compilation scheme for parallel processing near fine-grain tasks, each of which consists of several instructions or a statement, on a multiprocessor system called OSCAR. The scheme allows one to minimize synchronization and data transfer overheads and to optimally use registers of each processor by employing a static scheduling algorithm considering data transfer. This scheme can effectively be combined with macro-dataflow computation and with making the loop concurrent. A compiler using the proposed scheme has been implemented on OSCAR, which has been designed to take full advantage of the static scheduling. A performance evaluation of the scheme on OSCAR is also described.>

A parallel-processing scheme is described for robot-arm control computation on any number of parallel processors. The scheme employs two multiprocessor scheduling algorithms called, respectively, depth first/implicit heuristic search (DF/IHS) and critical path/most immediate successors first (CP/MISF); these were recently developed by the authors. The scheme is applied to the parallel processing of dynamic control computation for the Stanford manipulator. In particular, the proposed algorithms are applied to the computation of the Newton-Euler equations of motion for the Stanford manipulator and implemented on a multimicroprocessor system. The test result was so successful that the use of six processor pairs in parallel could attain the processing time of 5.37 ms. It is also shown that the proposed parallel-processing scheme is applicable to an arbitrary number of processors.

This paper describes practical optimization/ approximation algorithms for scheduling a set of partially ordered computational tasks onto a multiprocessor system so that the schedule length will be minimized. Since this problem belongs to the class of ''strong'' NP-hard problems, we must foreclose the possibility of constructing not only pseudopolynomial time optimization algorithms but also fully polynomial time approximation schemes unless P = NP. This paper proposes a heuristic algorithm named CP/MISF (critical path/most immediate successors first) and an optimization/approximation algorithm named DF/IHS (d thfirst/implicit heuristic search). DF/IHS is an excellent scheduling method which can reduce markedly space complexity and average computation time by combining the branch-and-bound method with CP/MISF; it allows us to solve very large scale problems with a few hundred tasks. Numerical examples are included to demonstrate the effectiveness of the proposed algorithms.