A fundamental problem in the theory of real-time scheduling is examined: scheduling a set of periodic or sporadic tasks on a uniprocessor without preemption and without inserted idle time. The authors give a necessary and sufficient set of conditions C for a set of periodic or sporadic tasks to be schedulable for arbitrary release times of the tasks. They show that any set of periodic or sporadic tasks that satisfies C can be scheduled with an earliest-deadline-first (EDF) scheduling algorithm. The authors present the scheduling model, briefly review the literature in real-time scheduling, prove that the non-preemptive EDF algorithm is universal for sets of tasks, whether periodic or sporadic, and demonstrate the absence of a universal algorithm for periodic tasks with specified release times. It is proved that the problem of deciding schedulability of a set of concrete periodic tasks is intractable.>

Abstract We define a linear graph to be a connected acyclic graph each of whose nodes is of degree one or two. We consider a flow problem in linear graphs in which a commodity flows from source nodes to sink nodes. Each source node has a specified value denoting an amount of a commodity to be disposed of and each sink node has a specified capacity denoting the maximum amount of the commodity it can absorb; edges are capable of carrying an arbitrary quantity of the commodity. A solution is a set of flows which transports the commodity from all source nodes to sink nodes without overfilling any sink. A solution is defined to be optimal if it is minimax, that is, the largest flow along any edge is as small as possible. We describe 0(n2) and 0(n) algorithms for finding optimal solutions.

A modification of conventional training techniques for linear threshold dichotomous pattern recognition is described. The modification is capable of convergence in some cases where the classical training techniques are not. The utility of this technique for signal detection problems is discussed.

Section 1 of this paper presents the basic mathematical definitions for our work. Section 2 defines the notion of a weighted phrase-structure grammar over either a semiring or zero monoid coefficient structure. The notion of canonical derivations (from Griffiths [1968]) and top-down derivations is defined in section 3, along with some of their basic properties. Equivalence relations over weighted phrase-structure grammars are defined in section 4 as well as power series representations of the associated languages.