Sequence analysis is an important research method in bioinformatics. Constant time solutions on BSR can be found in the literature to many applications. In this paper, some problems of sequence analysis are involved, and the constant time solutions on BSR to them are proposed, which is the first constant time solutions to the problems on any model of computation

Constant time solutions on BSR can be found in the literature to many applications, such as parenthesis matching, tree decoding, tree reconstruction, and etc. However, the problem of encoding a tree in constant time on BSR is still open. In this paper, some properties will be discussed on binary search trees and the i-p sequence, and based on the properties, a constant time algorithm on BSR is proposed for encoding a binary search tree into its i-p sequence, which is the first constant time solution to the problem on any model of computation.

In April 2002, the Faculty of Information Science of Kyushu Sangyo University was established, and started a new computer science program for undergraduate level. During the construction of the IS building, a set of video-camera and microphone was installed in every lecture room, in order to record all the lectures conducted by all teaching members of the Faculty of Information Science. The recorded lectures are distributed through the Web although its access is restricted within the campus. We call this system, lecture recording system. The introduction of the system was not intended to specify teaching or learning methods in advance, but is envisioned that such an educational environment with the system in place can provide the chance for students to review all the given lectures. And also, for the faculty members to review their own lectures as well as view the lectures of their co-faculty members so as to improve one's lecture and gain teaching skills. This paper reports on how this educational environment is operated and used.

Deadlock is one of the most serious and complex problems concerning the reliability of concurrent Java programs. In this paper, we discuss how to dynamically detect deadlocks in concurrent Java programs at run-time, and propose a representation of synchronization waiting state in an execution of a Java program, which is named the Java thread-wait-for graph. We explicitly define all types of deadlocks in Java with this representation and present an algorithm to detect the deadlocks. Two implementation methods are also presented. We succeeded in detecting a deadlock from a concurrent program, including all types of synchronization waiting relations, using our tool.

In this paper we describe a program analysis system called CLPKIDS, that is based on program dependence analysis, to support development of software engineering tools for understanding, testing, debugging, maintenance and complexity measurement of concurrent logic programs.

The authors propose a program dependence model for concurrent logic programs. They present three types of primary program dependences named the sharing dependence, communication dependence, and unification dependence between arguments in a concurrent logic program. We formally define these primary program dependences based on mode information. We further present a dependence-based representation named the argument dependence net (ADN), which explicitly represents all primary program dependences between arguments in a concurrent logic program. We also discuss some applications of the ADN for developing software engineering tools of concurrent logic programs. Finally, we briefly introduce a program analysis system called CLPKIDS for concurrent logic programs, which is a prototype implementation of the techniques introduced.

Takaoka has recently proposed two loopless algorithms for generating well formed parenthesis strings with length $2n$ and combinations $\mathcal{C}(r,n)$ of $n$ elements out of $r$ elements, respectively. O(1) time algorithms for generating $\mathcal{C}(r,n)$ in canonical representation that were found in the literature cannot list combinations with the Strong Minimal Change Property (SMCP), Eades and McKay's algorithm can generate $\mathcal{C}(r,n)$ in canonical representation with SMCP, but needs O$(n)$ worst-case time per combination. In this paper, we mainly discuss some orders with SMCP for $\mathcal{C}(r,n)$ in canonical representation, and give a loopless algorithm to generate $\mathcal{C}(r,n)$ in canonical representation with SMCP. We also give a loopless algorithm to list well formed parenthesis strings with length $2n$. Our two algorithms are more efficient in both space and time than Takaoka's two algorithms, respectively. In addition, our algorithms can be modified easily to generate objects in some different orders.

Constant time solutions for many applications have been obtained on BSR, but some theoretical problems on BSR (broadcasting with selective reduction) that raised when BSR was proposed have not been solved. Three of them are: 1) No lower bound for any problem on BSR is known except trivial constant time, 2) is there any improvement with nonconstant BSR time but still better than the lower bound for CRCW?, and 3) how to characterize problems for which BSR achieves constant time performance. In this paper, we have solved these three problems. For Problem 1, a lower bound on BSR is shown for any computational problem with an optimal sequential solution. An efficient sorting algorithm answers the second problem. A necessary condition is given for the third problem. The work-time (WT) scheduling principle and optimality for BSR are also introduced for investigating the BSR performance when the number of processors available, p, is different from the input size, n, of problems.

Large-scale and highly reliable concurrent systems are more and more required and it is indispensable for them to keep on measuring and monitoring in order to ensure their reliability. Some systematic method for developing self-measurement concurrent systems has been needed. Self-measurement programs may be difficult to be developed and maintained in a conventional environment for development. This paper presents the concept of the measurement handler, which is an approach to support development of self-measurement systems with programming languages. As a concrete example, we present the programming language Ada MH, which is an extension of Ada 95 with the measurement handler. In this paper, implementation of a processing system for Ada MH is also presented.

A recursive algorithm GenWordsR and a non-recursive algorithm GenWordsNR are presented in this paper to generate sequences for regular k-ary trees efficiently. They are compared with some of the previous recursive and non-recursive algorithms for this problem that were found in the literature. When the average number of recursive calls is used as a measure of the time complexity of recursive algorithms for generating k-ary trees, O(k) calls for a k-ary tree is the bestresult in the previous recursive algorithms, while O(1/k) calls for a k-ary tree is needed by GenWordsR. When the average number of comparisons is used as a measure of the time complexity of non-recursive algorithms for generating k-ary trees, GenWordsNR outperforms the previous non-recursive algorithms. As k increases, the number (and the average number) of comparisons performed by GenWordsNR tends to 66% that of the best previous non-recursive algorithms.

An explicit representation of various dependence relationships in a program has many applications in software engineering. The System Dependence Net is a model to represent program dependences in a concurrent program which consists of multiple procedures. The paper explains how to generate a System Dependence Net for Ada 95 programs automatically.

Traditional operating systems control the sharing of the processor resources among processes using a fixed scheduling policy based on the utilization of a computer system such as real time or timesharing systems. Since the control over the processor allocation is based on a fixed policy, not based on process execution behavior, this can hinder an effective use of a processor or can extend the processing time of a process unnecessarily. Thus, we proposed a couple of process scheduling policies which respond to process execution behavior. One of these policies is the policy for improving a Web server's response time. This policy controls multiple processes of a Web server by adjusting the execution of these processes according to their predicted behavior. We evaluated the performance of a Web server using this policy in simple cases. We evaluate the performance of a Web server when it is busy which is likely to be a realistic case. This could be the case in which it is most desirable to improve the response time of a Web server. Our experimental results show that the mean response times are improved greatly (up to 33.8% in the best case). They also show that the scheduling parameter is effectively predicted and updated by our mechanism based on the Web server's execution behavior.

BSR (Broadcasting with Selective Reduction) is a PRAM more powerful than any CRCW PRAM. In order to extend the Broadcast Instruction of BSR and make it more useful for a large class of applications, this article permits it to use a general form of selection, specifically, an arbitrary relational expression. BSR with general selection is denoted by BSR/sup +/. Thus, BSR or BSR with k criteria (k>1) is BSR/sup +/ in a special case. An efficient implementation for the Broadcast Instruction of BSR/sup +/ is proposed, requiring (1/k)th of the circuits used by the best previous implementation of BSR with k criteria. Of all PRAMs, BSR/sup +/ is the most powerful in computation.

Test-cases play an important role for high quality of software testing. Inadequate test-cases may cause bugs remaining after testing. Overlapped ones lead to the increases in testing costs. This paper proposes the Event InterActions Graph (EIAG) representing behavior of concurrent programs including any task-type and the cooperated paths (copaths) on the EIAG as test-cases, and describes the test-case generation tool (TCgen) for concurrent programs written in Ada programming language. The EIAG consists of Event Graphs and Interactions. An Event Graph is a control flow graph of a program unit in a concurrent program. The interactions represent interactions such as synchronizations between the program units. TCgen generates test-cases as copaths from an Ada concurrent program. The generated copaths satisfy given testing criteria. They can find some communication errors in testing and detecting unreachable statements which concern interactions. It is, however, necessary to validate feasibility of the generated copaths.

Supporting rapid response to changing customer requirements, reduction in both time and cost of manufacturing process, and integration within a heterogeneous wide area networked enterprise are necessary to increase worldwide competitiveness in manufacturing. We propose a CORBA based architecture to realize that manufacturing environment. We have developed an ORB for PLC to realize that architecture. And we have developed two prototypes of a remote monitoring system for factory automation, which are a manufacturing line monitoring system and a remote PLC monitoring system which uses a Web browser, to examine feasibility and effectiveness of the proposed architecture. According to experiments with these prototypes, we show the feasibility and effectiveness of our proposed CORBA based architecture.

In this paper we describe an application of design patterns to the development of a decision tree learning system. A decision tree learning system constructs a classifier as a form of tree from a given data set. It is required to be as flexible as possible when used in real application domains. Design patterns help us construct reusable software components and construct flexible and extensible systems. The approach employed in this study is as follows. First we examine several decision tree learning systems and identify hot-spots in the systems at points we anticipate future demand for modification and extension of the system. Second we determine which design pattern to apply to each hot-spot. We evaluate the extensibility of the system experimentally. Our experience shows that using design patterns in object-oriented software design allows the easy construction of flexible systems.

A task-type in concurrent programs is a template of task-instances which are dynamically generated in execution of the programs. The number of the generated task-instances may not be statically determined. Therefore, test-cases generated by our previously proposed method may not be realized in execution of the programs. This paper proposes an enhanced test-case generation method. Concurrent programs are classified into four kinds under two viewpoints, whether the number of task-instances generated from a task-type can be determined statically or dynamically, and whether or not the task-instances communicate with each other. The enhanced method uses a modified Event InterActions Graph (EIAG). The EIAG consists of event graphs and interactions. An event graph is an abstract control flow graph of a program unit. The interactions represent interactions between the units. Because the modified EIAG represents more accurate behavior of a program than the EIAG does, test-cases generated by the enhanced method increase the possibility of realizing themselves. The test-cases in the method increase in number. The method, however, is practical in the sense that the number of task-instances generated from a task-type is restricted.

In contrast to traditional integer sequences for the representation of binary trees, a kind of character sequence (words) is presented for binary trees based on a grammar GBT and for full binary trees based on a grammar GFBT. The properties of words derived from GBT (GFBT) are discussed in depth, including necessary and sufficient conditions for a word, prefix and suffix of Ł(GBT) (Ł(GFBT)) and algorithms are given and analysed for the enumeration of words of Ł(GBT) (Ł(GFBT)) lexicographically and in other ways. By modifying an algorithm for the enumeration of words in Ł(GBT), an algorithm is obtained to enumerate binary trees with a computer representation in an average time of O(1) per tree. The problem with non-isomorphic series of binary trees is also discussed within the category of a grammar.

Testing of concurrent programs is much more difficult than that of sequential programs. A concurrent program behaves nondeterministically, that is, the program may produce different results with the same input data according to execution timings of the program. In testing of concurrent programs, test data must specify not only input data but also sequences of statements. Ordered Sequence Testing Criterion for length k (OSC/sub k/), which was proposed by the authors, requires execution of all sequences of length k of concurrency statements which cause concurrent actions in a concurrent program. A monitoring tool has been developed for applying the testing criterion OSC/sub k/ to the testing of C concurrent programs on UNIX system. The tool measures coverage with regard to k-tuples of concurrency statements (OSC/sub k/) in source codes of a C concurrent program using a probe insertion method. The analysis of the tool's output for a practical C concurrent program shows not only applicability of the tool for testing of concurrent program but also the necessity of a supporting tool for forcing execution of concurrency statements.

Software testing generally proceeds as follows: generating test-cases, selecting test-data, executing a test target program, inspecting execution result and evaluating whether testing has already been sufficient or not yet. As for methods for structural testing of programs, the way using a coverage, where the coverage means what extent given testing criteria are satisfied, is noted. At the evaluating step, whether or not we finish the testing is determined in view of the coverage. This paper proposes a method for structural testing of concurrent programs written in Ada programming language, especially, test-case generation and execution of the programs. The Event InterActions Graph (EIAG) is used as a model for concurrent programs. The EIAG consists of Event Graphs and Interactions. An Event Graph is a control flow graph of a program unit in a concurrent program. The Interactions represent interactions between the program units. Program units are such as procedures, functions and task-types. After generating test-cases on the EIAG, a method for selecting test-data is described and measures to cope with infeasible test-cases with which are generated in this step is clarified. And a forced execution of a test target concurrent program in order to solve the nondeterministic execution is investigated. The nondeterministic execution is characteristic of concurrent programs.

Program slicing has many applications such as program debugging, testing, maintenance, and complexity measurement. This paper concerns the problem of slicing concurrent object-oriented programs that has not been addressed in the literatures until now. To solve this problem, we propose a new program dependence representation named the system dependence net (SDN), which extends previous program dependence representations to represent concurrent object-oriented programs. An SDN of a concurrent object-oriented program consists of a collection of procedure dependence nets each representing a main procedure, a free standing procedure, or a method in a class of the program, and some additional arcs to represent direct dependences between a call and the called procedure/method and transitive interprocedural data dependences. We construct the SDN to represent not only object-oriented features but also concurrency issues in a concurrent object-oriented program. Once a concurrent object-oriented program is represented by its SDN, the slices of the program can be computed based on the SDN as a simple vertex reachability problem in the net.

In this paper a formal model for program dependence analysis of concurrent logic programs is proposed with the following contributions. First, two language-independent program representations are presented for explicitly representing control flows and/or data flows in a concurrent logic program. Then based on these representations, program dependences between literals in concurrent logic programs are defined formally, and a dependence-based program representation named the Literal Dependence Net (LDN) is presented for explicitly representing primary program dependences in a concurrent logic program. Finally, as applications of the LDNs, some important software engineering activities including program slicing, debugging, testing, complexity measurement, and maintenance are discussed in a programming environment for concurrent logic programs.

Almost all, if not all, software development and maintenance activities require some abstract representations for target programs in order to grasp necessary information about the programs and ignore unnecessary information. This paper presents the role of unified program representations in distributed software development, basic considerations on constructing an integrated environment for supporting distributed software development based on unified program representation, and the design and implementation of an integrated environment we are developing.

Test cases play an important role for high-quality software testing. Inadequate test-cases may cause bugs to remain after testing. Overlapped test cases may increase costs. This paper proposes an event interactions graph (EIAG), representing the behavior of concurrent programs and the cooperated paths (copaths) on the EIAG as test cases. The EIAG consists of event graphs and interactions. An event graph is a control flow graph of a program unit in a concurrent program. The interactions are synchronizations, communications and waits between the program units. Copaths can be generated automatically by the algorithms which are presented in this paper. The generated copaths can detect dead (unreachable) statements and can find some communication errors in testing. However, it is necessary to validate the feasibility of the generated copaths.

Testing of programs is important to increase the reliability of programs. Coverage is a ratio of the number of worked test events to all test events, and it is used as a metric of testing sufficiency and reliability. The test events are defined by a testing criterion. Some testing criteria are proposed for evaluating testing sufficiency of sequential programs. However, the criteria are inadequate for concurrent programs. New testing criteria must be introduced for concurrent programs. The paper proposes new testing criteria, ordered sequence criteria (OSC) for concurrent programs. OSC are concerned with interprocess communication and synchronization. An OSC/sub k/ selects k-length sequences of statements related to communication or synchronization. The sequences should be executed at least once in testing. OSC/sub k/ presents various levels of testing according to values of k. The OSC/sub 2/ is reliable for a program which is correct or which includes communication errors. A prototype is implemented for coverage measuring based on OSC/sub 2/.>

A tasking deadlock detector for Ada programs is presented. The software tool works by monitoring the tasking behavior of a target program and operating a task-wait-for graph for the program. It can detect all types of tasking deadlocks in a class of Ada programs. The authors describe the principle of detecting tasking deadlocks dynamically, present their implementation of the tool, and give a real example of using the tool to detect a complex taking deadlock.>

A problem in knowledge engineering is investigated in order to determine how to generate automatically new valid causal relations from some known causal relations (e.g. given with the IF-THEN form). The authors discuss this problem from a logical viewpoint and propose using the entailment that is a primitive logical basis for the incremental generation of causal relations. After a brief comparison between relevance logics and entailment logic, the authors define a subclass of entailment logic, given an algebraic model for it, show its soundness based on the model, and discuss deductive entailment reasoning based on the logic. As a result, for given causal relations, new valid causal relations can be generated by deductive entailment reasoning based on the logic.>

Abstract This paper shows how helpful a tool for stepwise improvement of programs an execution profiler is. As a demonstration we develop an efficient program for getting the sum of n addends by using Huffman's algorithm. Rewriting an old version of a program step by step, using as a guide information about its dynamic behaviour obtained by the profiler, we finally get an efficient program whose CPU time is reduced to about 1/20 of the first version's for n = 200.