This paper deals with the constrained DAG shortest path problem (CDSP), which finds the shortest path on a given directed acyclic graph (DAG) under any logical constraints posed on taken edges. There exists a previous work that uses binary decision diagrams (BDDs) to represent the logical constraints, and traverses the input DAG and the BDD simultaneously. The time and space complexity of this BDD-based method is derived from BDD size, and tends to be fast only when BDDs are small. However, since it does not prioritize the search order, there is considerable room for improvement, particularly for large BDDs. We combine the well-known A* search with the BDD-based method synergistically, and implement several novel heuristic functions. The key insight here is that the ‘shortest path’ in the BDD is a solution of a relaxed problem, just as the shortest path in the DAG is. Experiments, particularly practical machine learning applications, show that the proposed method decreases search time by up to 2 orders of magnitude, with the specific result that it is 2,000 times faster than a commercial solver. Moreover, the proposed method can reduce the peak memory usage up to 40 times less than the conventional method.

The present study investigated the performance of text-based explanation for a large number of learners in an online tutoring task guided by a Pedagogical Conversational Agent (PCA). In the study, a lexical network analysis that focused on the co-occurrence of keywords in learner's explanation text, which were used as dependent variables, was performed. This method was used to investigate how the variables, which consisted of expressions of emotion, embodied characteristics of the PCA, and personal characteristics of the learner, influenced the performance of the explanation text. The learners (participants) were students enrolled in a psychology class. The learners provided explanations to a PCA one-on-one as an after-school activity. In this activity, the PCA, portraying the role of a questioner, asked the learners to explain a key concept taught in their class. The students were randomly assigned one key term out of 30 and were asked to formulate explanations by answering different types of questions. The task consisted of 17 trials. More than 300 text-based explanation dialogues were collected from learners using a web-based explanation system, and the factors influencing learner performance were investigated. Machine learning results showed that during the explanation activity, the expressions used and the gender of the PCA influenced learner performance. Results showed that (1) learners performed better when a male PCA expressed negative emotions as opposed to when a female PCA expressed negative emotions, and (2) learners performed better when a female PCA expressed positive expressions as opposed to when a female PCA expressed negative expressions. This paper provides insight into capturing the behavior of humans performing online tasks, and it puts forward suggestions related to the design of an efficient online tutoring system using PCA.

We introduce a graphical calculus for multi-qutrit systems (the qutrit ZX-calculus) based on the framework of dagger symmetric monoidal categories. This graphical calculus consists of generators for building diagrams and rules for transforming diagrams, which is obviously different from the qubit ZX-calculus. As an application of the qutrit ZX-calculus, we give a graphical description of a (2, 3) threshold quantum secret sharing scheme. In this way, we prove the correctness of the secret sharing scheme in a intuitively clear manner instead of complicated linear algebraic operations.

Many studies and systems that incorporate elements such as “pleasure” and “fun” in the game to improve a learner's motivation have been developed in the field of learning environments. However, few are the studies of situations where many learners gather at a single computer and participate in a game-based learning environment (GBLE), and where the GBLE designs the learning process by controlling the interactions between learners such as competition, collaboration, and learning by teaching. Therefore, the purpose of this study is to propose a framework of educational control that induces and activates interaction between learners intentionally to create a learning opportunity that is based on the knowledge understanding model of each learner. In this paper, we explain the design philosophy and the framework of our GBLE called “Who becomes the king in the country of mathematics?” from a game viewpoint and describe the method of learning support control in the learning environment. In addition, we report the results of the learning experiment with our GBLE, which we carried out in a junior high school, and include some comments by a principal and a teacher. From the results of the experiment and some comments, we noticed that a game may play a significant role in weakening the learning relationship among students and creating new relationships in the world of the game. Furthermore, we discovered that learning support control of the GBLE has led to activation of the interaction between learners to some extent.

This research aims to accelerate the computation module in max-plus algebra using CUDA technology on graphics processing units (GPUs) designed for high-performance computing. Our target is the Kleene star of a weighted adjacency matrix for directed acyclic graphs (DAGs). Using a inexpensive GPU card for our experiments, we obtained more than a 16-fold speedup compared with an Athlon 64 X2.

This research proposes efficient calculation methods for the transition matrices in discrete event systems, where the adjacency matrices are represented by directed acyclic graphs. The essence of the research focuses on obtaining the Kleene Star of an adjacency matrix. Previous studies have proposed methods for calculating the longest paths focusing on destination nodes. However, in these methods the chosen algorithm depends on whether the adjacency matrix is sparse or dense. In contrast, this research calculates the longest paths focusing on source nodes. The proposed methods are more efficient than the previous ones, and are attractive in that the efficiency is not affected by the density of the adjacency matrix.

Most heuristics for the task scheduling problem employ a simple model of the target system, assuming fully connected processors, a dedicated communication subsystem and no contention for communication resources. A small number of algorithms is aware of the contention, using an undirected graph model of the communication network. Although, many scheduling algorithms have been compared in the literature, little is known about the accuracy and appropriateness of the employed models. This article evaluates the accuracy of task scheduling algorithms on generic parallel systems. The performed experiments show a significant inaccuracy of the schedules produced. In an extensive analysis, the reasons for these results are identified and the implications for the scheduling model are discussed.

A parallel program with a fixed degree of parallelism cannot be executed efficiently, or at all, by a parallel computer with a different degree of parallelism. This will cause a problem in the distribution of software applications in the near future when parallel computers with various degrees of parallelism will be widely used. In this paper we propose a way to make the machine code of the programs parallelism-independent, i.e. executable in minimum time on parallel computers with any degree of parallelism. We propose and evaluate three parallelism-independent scheduling algorithms for direct acyclic graphs (DAGs) of tasks with non-uniform execution times. To prove their efficiency, we performed simulations both with random DAGs and DAGs extracted from real applications. We evaluate them in terms of schedule length, computation time and size of the scheduled program. Their results are compared to those of the traditional CP/MISF algorithm which is used separately for each number of processors.

Scheduling directed a-cyclic task graphs (DAGs) onto multiprocessors is known to be an intractable problem. Although there have been several heuristic algorithms for scheduling DAGs onto multiprocessors, few address the mapping onto a given number of completely connected processors with an objective of minimizing the finish time. We present an efficient algorithm called ClusterMerge to statically schedule directed a-cyclic task graphs onto a homogeneous completely connected MIMD system with a given number of processors. The algorithm clusters tasks in a DAG using a longest path heuristic and then iteratively merges these clusters to give a number of clusters identical to the number of available processors. Each of these clusters is then scheduled on a separate processor. Using simulations, we demonstrate that ClusterMerge schedules task graphs yielding the same or lower execution times than those of other researchers, but using fewer processors. We also discuss pitfalls in the various approaches to defining the longest path in a directed a-cyclic task graph.

All the existing scheduling algorithms order the instructions of the program in such a way that it can be executed in minimal time only for one fixed number of processors. In this paper we propose a new scheduling method, called Parallelism-Independent Scheduling Method, which enables the execution of the scheduled program on parallel computers with any degree of parallelism in near-optimal time. We propose three Parallelism-Independent algorithms, which have the following phases: obtaining a parallel schedule by using a list scheduling heuristics, optimization of the parallel schedule by rearranging the tasks in each level, so that they can be executed efficiently with different degrees of parallelism, serialization of the parallel schedule, and insertion of markers for the parallel execution limits. The three algorithms differ in their optimization phase. To prove the efficiency of our algorithms, we have made simulations with random directed acyclic graphs with different size and degree of parallelism. We compared the results in terms of schedule length to those obtained using the Critical Path Algorithm separately for each degree of parallelism.

Topological sorting is, given with a directed acyclic graph G = (V, E), to find a total ordering of the vertices such that if (u, v) E then u is ordered before v. Instead of finding total orderings, we wish to find out how many total orderings exist in a given directed acyclic graph G = (V, E). Here we call a total ordering as legal sequence and the problem as legal sequence number problem. In this paper, we first propose theorems on equivalent transformation of graphs with respect to legal sequence number. Then we give a formula to calculate legal sequence number of basic series-parallel digraphs and a way of the calculation for general series-parallel digraphs. Finally we apply our results to show how to obtain legal sequence number for a class of extended series-parallel digraphs.

In high performance compilers to process pointer-handling programs, precise pointer alias analysis is useful for the compilers to generate efficient object code. It is well known that most compiler techniques such as data flow analysis, dependence analysis, side effect analysis and optimizations are related to the alias problem. However, without data structure information, there is a limit on the precision of the alias analysis. Even though the automatic data structure detection problem is complex, when pointer manipulation satisfies some restrictions, some data structures can be detected automatically by compilers with some knowledge of aliases. In this paper, we propose an automatic data structure detection method for Pascal and Fortran 90. Linear list, tree and dag data structures are detected. Detected data structure information can be used not only for raising the precision of alias analysis but also for some optimizing techniques for pointer handling programs directly.