leff@smu.CSNET (Laurence Leff) (10/25/87)
Single copies of the following reports at no charge may be obtained by writing to (U.S. mail): Technical Reports Computer Science Department Washington State University Pullman, WA 99163-1210 U.S.A. %R CS-86-163 %D 1986 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %T NONCONSTRUCTIVE TOOLS FOR PROVING POLYNOMIAL-TIME DECIDABILITY %A Michael R. Fellows %A Michael A. Langston %X Recent advances in graph theory and graph algorithms dramatically alter the traditional view of concrete complexity theory, in which a decision problem is generally shown to be P by producing an efficient algorithm to solve an optimization version of the problem. Nonconstructive tools are now available for classifying problems as decidable in polynomial time by guaranteeing only the \fIexistence\fP of polynomial-time \fIdecision\fP algorithms. In this paper, these new methods are employed to prove membership in P for a number of problems whose complexities are not otherwise known. Powerful consequences of these techniques are pointed out and their utility is illustrated. A type of partially ordered set which supports this general approach is defined and explored. %R CS-87-164 %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %T RESOURCE ALLOCATION UNDER LIMITED SHARING %A Michael A. Langston %A Michael P. Morford %X We study the problem of resource sharing within a system of users, each with the same resource capacity, but with varying resource demands. For model simplicity, we assume system saturation, so that the total demand matches the total capacity, and permit only a limited form of sharing in which a user is free to share its unused capacity with exactly one other user. We seek to maximize the total amount of unshared capacity over all feasible solutions, reflecting an environment in which sharing incurs a cost proportional to the overall quantity shared. For the general problem, which is NP-hard, we derive a tight worst-case performance bound for a greedy algorithm, G, as well as for a number of other sharing rules. We also prove several results concerning G's behavior in more restricted settings. %R CS-87-165 %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %T ON-LINE VARIABLE SIZED BIN PACKING %A Nancy G. Kinnersley %A Michael A. Langston %X The classic bin packing problem is one of the best-known and most widely-studied problems of combinatorial optimization. Efficient, off-line approximation algorithms have recently been designed and analyzed for the more general and realistic model in which bins of differing capacities are allowed /Friesen and Langston, ``Variable Sized Bin Packing,'' \fISIAM J. on Computing\fP 15(1986), 222-230/. In this paper, we consider fast \fIon-line\fP algorithms for this challenging model. Selecting either the smallest or the largest available bin size to begin a new bin as pieces arrive turns out to yield a tight worst-case ratio of 2. We devise a slightly more complicated scheme, which uses the largest available bin size for small pieces, and selects bin sizes for large pieces based on a user-specified fill-factor f >= 1/2, and prove that this strategy guarantees a worst-case bound not exceeding 1.5 + f/2. %R CS-87-166 %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %T STABLE SET AND MULTISET OPERATIONS IN OPTIMAL TIME AND SPACE %A Bing-Chao Huang %A Michael A. Langston %X The focus of this paper is on demonstrating the existence of methods for stably performing set and multiset operations on sorted files of data in both optimal time and optimal extra space. It is already known that stable merging and stable duplicate-key extraction permit such methods. The major new results reported herein are these: 1. an asymptotically optimal time and space algorithm is devised to stably select matched records from a sorted file, 2. this selection strategy is employed, along with other algorithmic tools, to prove that all of the elementary binary set operations can be stably performed in optimal time and space on sorted files, and 3. after generalizing these operations to multisets in a natural way for file processing, it is proved that each can be stably performed in optimal time and space on sorted files. %R CS-87-167 BISIMULATION OF AUTOMATA %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %A David B. Benson %A Ofer Ben-Shachar %X We view CCS terms as defining certain automata. An algebraic representation of automata is given, and a category of automata and simulations between them is defined. The epimorphisms between the automata partition the category into bisimulation equivalence classes. These are a unique canonical representative for each bisimulation equivalence class. These results hold for weak bisimulation and hence for strong bisimulation. Essentially the same results are obtained with regard to rooted bisimulation equivalence classes of automata which have start states. %R CS-87-168 %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %T THE SHUFFLE BIALGEBRA %A David B. Benson %X The \fIshuffle\fP multiplication and the \fI cut\fP comultiplication, a generalized car-cdr pairing, form a bialgebra. The \fI concatenation\fP multiplication, sometimes called tensor product, and the \fI spray\fP comultiplication form another bialgebra. The concatenation-spray bialgebras are the free bialgebras in the category of precise, graded bialgebras over a semiadditive symmetric monoidal category. The shuffle-cut bialgebras are the cofree bialgebras in the same category of bialgebras. These categories include many of the settings of interest in the theories of formal languages and the theories of distributed, concurrent and parallel computation. We analyze the \fI marked shuffle\fP, of interest in theories of distributed computing, in terms of its resolutions into the cofree shuffle-cut bialgebra. %R CS-87-169 %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %T BIALGEBRAS: SOME FOUNDATIONS FOR DISTRIBUTED AND CONCURRENT COMPUTATION %A David B. Benson %X A categorical bimonoid consists of a monoid and a comonoid which act homomorphically on one another. In applications bimonoids are typically called bialgebras or Hopf algebras. The definitions are given at a level suitable to computer science applications and many examples are included. The elements of the theory of graded bialgebras are developed. With this theory we explicate the refinements of concurrent programs via graded subalgebras of the graded shuffle. The concluding section characterizes all coalgebras which interact with the match algebra to form a bialgebra and characterizes all algebras which interact with the fork (diagonal) coalgebra to form a bialgebra. %R CS-87-170 FAST STABLE MERGING AND SORTING IN CONSTANT EXTRA SPACE %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %A Bing-Chao Huang %A Michael A. Langston %X In an earlier research paper /Huang and Langston, ``Practical In-Place Merging,'' to appear in \fI Communications of the ACM\fP/, we presented a novel, yet straightforward linear-time algorithm for merging two sorted lists in a fixed amount of additional space. Constant of proportionality estimates and empirical testing reveal that this procedure is reasonably competitive with merge routines free to squander unbounded additional memory, making it particularly attractive whenever space is a critical resource. In this paper, we devise a relatively simple strategy by which this efficient merge can be made stable, and extend our results in a nontrivial way to the problem of stable sorting by merging. We also derive upper bounds on our algorithms' constants of proportionality, suggesting that in some environments (most notably external file processing) their modest run-time premiums may be more than offset by the dramatic space savings achieved. %R CS-87-171 %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %T POLYNOMIAL-TIME SELF-REDUCIBILITY: THEORETICAL MOTIVATIONS AND PRACTICAL RESULTS %A Donna J. Brown %A Michael R. Fellows %A Michael A. Langston %X Although polynomial-time complexity theory has been formulated in terms of decision problems, a typical polynomial-time decision algorithm generally operates by actually constructing a solution to an optimization version of the problem at hand. Thus it is that \fI self-reducibility\fP, the process by which a decision algorithm may be used to devise a constructive algorithm, has until now been widely dismissed as a topic of theoretical interest only. Suddenly, however, dramatic advances in graph theory and graph algorithms have made available powerful new \fInonconstructive\fP tools which can be applied to guarantee membership in P. In fact, these tools are nonconstructive at two levels: they neither produce the decision algorithm, relying instead on the finiteness of an obstruction set, nor do they specify whether such a decision algorithm can be of any aid in the construction of a solution. We briefly review and expand the use of these tools, and discuss the seemingly formidable task of finding decision algorithms (obstruction sets). Our main focus is on the design of efficient self-reduction strategies, with combinatorial problems drawn from such diverse areas as topological embeddings, network reliability, and VLSI, as well as more straightforward graph problems. %R CS-87-172 %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %T LOGICS OF PROGRAMS %A Dexter Kozen %A Jerzy Tiuryn %X The paper presents a first full version of a chapter written for the forthcoming monography ``Handbook of Theoretical Computer Science'' to be published by North-Holland. It is viewed as an introduction and a review of the field of Logics of Programs. The main emphasis of the paper is on Dynamic Logic, both propositional and first-order. %R CS-87-173 %D 1987 %I Computer Science Department, Washington State University %C Pullman, WA 99163-1210 %T FIXED POINTS IN FREE PROCESS ALGEBRAS, PART I %A Jerzy Tiuryn %A David B. Benson %X The left simple polynomials over free process algebras are either \fIsemilinear\fP or \fI nonlinear\fP. The semilinear left simple polynomials are subdivided further into the classes of delta-semilinear, tau-semilinear, tau,delta-semilinear, and A-semilinear, depending upon the right multipliers of the variable x. The linear polynomials considered in Part I are a special case of tau-semilinear polynomials. For delta-semilinear polynomials p(x), p^5(x)=p^6(x). For the special case of tau,delta-semilinear polynomials in which the right multipliers lie in P(emptyset), p^6(x)=p^7(x). The solutions to x=p(x) for A-semilinear polynomials are completely characterized. As is demonstrated, the remaining semilinear cases remain unsettled. Necessary conditions for the solutions to x=p(x) for nonlinear left simple polynomials are given. In addition, for a certain subclass of the nonlinear polynomials, sufficient conditions are given. This paper depends upon Part I of the same title, CS-86-152.