Time-terms are used by humans to indicate a temporal frame of reference during communication with one another. The frame of time is used to indicate whether an action or event has happened in the past, is currently taking place, or will happen in the future. These terms may specify an amount of time in the form of a time difference value, a specific time moment or time period in the form of a time concept value, and a time relative to now in the form of time adverbs. In this paper, we describe how a computer program understands time terms when they are expressed in a sentence. Understanding a time-term means to find out exactly what the term stands for when it is used. We discuss what knowledge the program needs to acquire, and describe how the program uses this knowledge to recognize the various kinds of time-terms in a given sentence. We then discuss how the program understands them by classifying time concept values and time adverbs into the categories of time period and time moment. Finally, we present how to combine time-terms into a single time period or time moment when multiple terms are presented in a sentence introduced by various prepositions, e.g., at noon on Tuesday of next week. It allows the program to use the understanding to perform simple reasoning about the relationships, such as starts before or ends after, between two given time-terms or events.

Given a graph whose edges never fail but whose nodes fail independently of each other with a constant probability 1 − p, the reliability of a graph is defined to be the probability that the induced subgraph of the surviving nodes is connected. Let Ω (n, m) be the class of all graphs with n nodes and m edges. A graph G of Ω is said to be uniformly best in Ω, if for all choices of p, it is most reliable in the class of graphs, Ω. In this paper, the existing known set of uniformly best graphs is extended, and some closely related graphs are proved to be not the uniformly best graphs in their class. More precisely, we prove that for any positive integer b the complete tripartite graph K(b, b + 1, b + 2) is uniformly best in its class Ω(3b + 3, 3b2 + 6b + 2), while the complete tripartite graphs K(b, b + 1, b + i)(i > 2) are not the uniformly best in their classes Ω(3b + i + 1, 3b2 + 2(i + 1)b + i). © 2000 John Wiley & Sons, Inc.

This paper investigates the problem of nonreconfigurable, nonpreemptive scheduling of parallel tasks in a homogeneous system of processors. Given a task precedence graph where each task T may be executed on up to $\delta (T)$ processors, the problem is to find a schedule such that the makespan is minimized. A scheduling policy is nonreconfigurable if when more processors become available after a task T has been scheduled on p processors, $p < \delta (T)$, they cannot join the execution of task T. It is nonpreemptive if each task is executed without interruption until completion once the task has started execution. The problem of scheduling parallel tasks is NP-hard. The performance ratio of the makespan produced by the original list scheduling algorithm proposed by Graham [SIAM J. Appl. Math., 17 (1969), pp. 416–429] to the optimal makespan is $\Delta + \frac{m - \Delta} {m}$ [Inform. Process. Lett., 37 (1991), pp. 291–297], where m and $\Delta $ are the number of processors in the system and the maximum degree of parallelism in any task, respectively. To provide a performance improvement, the Earliest Completion Time (ECT) algorithm is proposed; it is also shown that its performance ratio is bounded by $3-\frac{2}{m}$. In addition, an example is presented to demonstrate that the bound is at least 2.5.

A simultaneous access design of a dictionary machine which supports insert, delete, and search operations is presented. The design is able to handle p accesses simultaneously and allows redundant accesses to occur. In the design, processors performing insert or delete operations are free to perform other tasks after submitting their accesses to the design; processors that perform search operations get their response in O(log N) time. Compared to all sequential access designs of a dictionary which require O(p) time to process p accesses, the presented design provides much higher throughput; specifically, O(p/log p) times better. It also provides a fast mechanism to avoid the sequential access bottleneck in any large multiprocessor system.>

The job scheduling problem in a partitionable mesh-connected system in which jobs require square meshes and the system is a square mesh whose size is a power of two is discussed. A heuristic algorithm of time complexity O(n(log n+log p)), in which n is the number of jobs to be scheduled and p is the size of the system is presented. The algorithm adopts the largest-job-first scheduling policy and uses a two-dimensional buddy system as the system partitioning scheme. It is shown that, in the worst case, the algorithm produces a schedule four times longer than an optimal schedule, and, on the average, schedules generated by the algorithm are twice as long as optimal schedules.>

The three-dimensional packing problem is discussed in this paper. The problem is a generalization of the one- and two-dimensional packing problems. It is demonstrated that some basic packing strategies such as NFDH and FFDH for two-dimensional packing have unbounded worst-case performance ratios in the three-dimensional case. Let $r(A)$ denote the asymptotic performance bound of an approximation algorithm A. An approximation algorithm G is developed, and it is shown that $4.333 \leqq r(G) \leqq 4.571$. The algorithm is improved to algorithm C and it is proven that $r(C) = 3.25$. For the special case when all boxes have square bottoms, the two algorithms are adapted to algorithms $G_1 $ and $C_1 $, respectively, with $r(G_1 ) = 4$ and $r(C_1 ) = 2.6875$. For the case when both sides of the bottom of a box are no larger then ${1 / m}$, two families of algorithms, $G^* _m (m \geqq 3)$ and $C^* _m (m \geqq 2)$, are presented. It is shown that $r(G^* _m ) = {m / {(m -2)}}$ and $r(C^* _m ) = {{(m+1)} / {(m-1)}}$. Similarly, when these small bottom boxes have square bottoms, there exist two families of algorithms, $G_m (m\geqq 2)$ and $C_m (m \geqq 2)$, such that $r(G_m )={(m / {(m-1)}})^2 $ and $r(C_m )=( {{(m+1)} / m} )^2 $.