eCommons Collection: Computer Science Technical Reports

A Linear List Merging Algorithm

Wed, 14 May 2008 13:42:16 GMT

Title: A Linear List Merging Algorithm

Authors: Hopcroft, John E.; Ullman, Jeffrey D.

Abstract: A linear list merging algorithm and its analysis is presented. Starting with n lists, each containing a single element, the algorithm will execute an arbitrary sequence of requests to merge lists and to find the name of the list currently containing a given element. If the length of the sequence of requests is bounded by a constant times n, then the execution time of the algorithm on a random access computer is bounded by a constant times n.

On the Modelling Power of Petri Nets

Wed, 28 Nov 1979 22:58:59 GMT

Title: On the Modelling Power of Petri Nets

Authors: Meiling, Erik

Abstract: The behavior of a Petri net is expressed as a formal language. Certain families of Petri net languages are characterized by propositions similar to the classical pumping theorems. The results are used to give examples of behaviors that cannot be expressed by languages in these families.

Cand and Cor Before and Then or Else in Ada

Mon, 29 Oct 1979 22:58:59 GMT

Title: Cand and Cor Before and Then or Else in Ada

Authors: Gries, David

Abstract: NO ABSTRACT SUPPLIED

A Proof Technique for Communicating Sequential Processes(With an Example)

Mon, 29 Oct 1979 22:58:59 GMT

Title: A Proof Technique for Communicating Sequential Processes(With an Example)

Authors: Levin, Gary Marc

Abstract: We present proof rules for an extension of the Communicating Sequential Processes proposed by Hoare. The send and receive statements are treated symmetrically, simplifying the rules and allowing send to appear in guards. An example is given to explain the use of the technique. This is an outline of a substantial part of a PhD thesis that is expected to be completed in June 1980.